=Paper=
{{Paper
|id=Vol-2404/paper21
|storemode=property
|title=A Peer-to-Peer Notification System for Distributed Online Social Networks
|pdfUrl=https://ceur-ws.org/Vol-2404/paper21.pdf
|volume=Vol-2404
|authors=Michele Amoretti,Lorenzo Gandolfi,Michele Tomaiuolo
|dblpUrl=https://dblp.org/rec/conf/woa/AmorettiGT19
}}
==A Peer-to-Peer Notification System for Distributed Online Social Networks==
https://ceur-ws.org/Vol-2404/paper21.pdf
Workshop "From Objects to Agents" (WOA 2019)
A Peer-to-Peer Notification System for Distributed
Online Social Networks
Michele Amoretti Lorenzo Gandolfi Michele Tomaiuolo
University of Parma, Italy University of Parma, Italy University of Parma, Italy
michele.amoretti@unipr.it lorenzo.gandolfi@studenti.unipr.it michele.tomaiuolo@unipr.it
Abstract—Current social networking systems are almost al- However, such P2P systems have to confront with the most
ways centralized systems. This architecture poses issues about convenient features provided by current social platforms, both
privacy, censorship and control of personal data. On the other in terms of functionalities and responsiveness. While some
hand, peer-to-peer systems can overcome these issues, in exchange
with additional architectural complexity. This paper describes a trade-offs are certainly to be considered, it is necessary to
peer-to-peer system provided with a spanning tree for distributing allow users of distributed social platforms to develop fluent
online notifications inside a group of interested peers. These online discussions, with notifications of new activities received
notifications may regard discussion messages for a chat system, with short and acceptable delays.
or any kind of update messages for spreading social activities In this paper, we describe specifically a P2P system pro-
performed by users of a Distributed Online Social Network. In
particular, we describe and compare different mechanisms for vided with a spanning tree for distributing online notifications
the creation and management of the spanning tree. inside a group of interested users. These notifications can
Index Terms—Distributed Systems, Online Social Network, regard discussion messages for a chat system, or any kind
Peer-to-Peer, Notification Systems. of update messages for spreading social activities performed
by users of a Distributed Online Social Network (DOSN) [7]–
I. I NTRODUCTION [10]. In particular, we describe and compare some mechanisms
for the creation and management of the spanning tree. With
Social media attracts millions of people, who in fact spend respect to similar approaches, our spanning tree does not
most of their online time social networking, for a variety rely on a specific P2P architecture, and does not require that
of everyday actions. Accordingly, these social platforms are all nodes of the underlying P2P network are fully involved
assuming different forms and aims, including distribution of in the DOSN. Any structured P2P network (such as Chord,
news, sharing of photos and videos, direct messaging, group Kademlia, or Pastry) could be used as a substrate for several
discussions, etc. [1]. Together with their mass spreading and partially overlapping spanning trees, each one corresponding
also in consequence of big scandals, social platforms are also to a specific group of users.
raising concern and criticism. In particular, many users are The manuscript is organized as follows. Section II analyzes
wary of privacy threats coming from other users, external the state of the art for P2P publish-subscribe systems. Section
entities, and also directly from the service providers. IV illustrates and proposes some algorithms for the creation
In fact, even if the social networking systems are greatly and management of a tree structure among peers. Section V
dissimilar in their user base and functionality [2], they are shows the results obtained by comparing the proposed different
almost always centralized systems, which often allow service mechanisms and policies. Finally, some concluding remarks
providers to: (i) mine user provided data for advertisements are provided in Section VI.
and other purposes, (ii) guide their users into “walled gardens”,
without full control over their own information [3], [4], (iii) II. R ELATED WORKS
perform a-priori or a-posteriori censorship [5], (iv) disclose all Castro et al. proposed Scribe [11], an application level
the information they have to other entities, either motivated by multicast infrastructure on top of the Pastry DHT, which is
selfish interests or forced under legal terms and other forms used in a number of projects for peer-to-peer collaboration
of pressure. and dissemination of information. Scribe creates and manages
Conversely, in exchange with additional architectural com- multicast groups on top of Pastry. Any Scribe node can create a
plexity, peer-to-peer (P2P) systems essentially achieve auto- group, providing a group ID and some credentials to be used
matic resource scalability, in the sense that the availability of for access control. Other nodes can then join the group or
resources is proportional to the number of users [6]. Moreover, send multicast messages, which are delivered to all members.
without a central entity, nobody is in the position of censoring Multicast messages are delivered by some forwarder nodes,
data systematically. Privacy can also be achieved, by means which form a multicast tree. Forwarder nodes themselves are
of key systems and cryptography. In a P2P system, if global not required to be part of the group, instead they automatically
trusted third parties are avoided, no entity has the ability to become forwarders if they are on the Pastry route of some new
disclose a user’s private key or other sensible credentials. member of the group, when it sends a join request.
142
Workshop "From Objects to Agents" (WOA 2019)
FeedTree [12] is an RSS (Real Simple Syndication) feed P2P network are fully involved in the DOSN. Structured P2P
distribution service based on P2P subscription mechanisms. networks like Chord, Kademlia, or Pastry, could serve as a
FeedTree proposes a transition toward pushing RSS items over substrate for partially overlapping spanning trees, each one
a P2P network, distributing the load over the nodes of a group corresponding to a specific group of users. That is, one peer
multicast tree. For this purpose, FeedTree exploits Pastry and may belong to different groups at the same time.
Scribe.
Xu et al. introduced Cuckoo [13] as a decentralized and III. D ISTRIBUTED SOCIAL ARCHITECTURES
socio-aware online micro-blogging service. It follows a hybrid The diffusion of online social networks is opening new
approach consisting of: (i) a structured overlay network, Pas- scenarios for envisaging novel kinds of applications, either to
try, and a gossip protocol for disseminating micro-news among support new social networking activities, or to exploit estab-
users with the same interests; and (ii) support for centralized lished relationships among users and use them to offer higher-
dedicated services, like Twitter, which in fact still store user level services. Software agents are a natural fit for mediating
profiles and other data. Friend nodes help each other to balance access to local software- or hardware-based services, including
load, thus creating a sort of virtual node. Notifications are dealt access to data, sensors, monitors, printers and various kinds
with direct push, in the case of normal users, or with gossip of actuators. Given their ability to negotiate and plan in a
propagation, in the case of celebrities and broadcasters. dynamic social context, software agents are also good for
Perfitt & Englert proposed Megaphone [14] as a micro- composing locally available services and resources, following
blogging system, based on an optimized, trustworthy peer-to- existing trust relationships with other persons and agents
peer network. In fact, nodes are enabled to sign and encrypt located in the users proximity area. New trust relationships
each piece of content they publish, making it verifiable and can also be created, on the basis of reputation and mutual
confidential for subscribers. The basic distribution mechanism acknowledgement, through the incremental and controlled
is based on Scribe multicast trees. Thus, a subscriber node has exchange of profile data.
to know in advance the node ID of the posters to follow, or
at least it has to be able to generate it. The poster’s node A. Autonomous agents for DOSNs
ID corresponds exactly to a Scribe multicast group ID. In Especially in the case of completely distributed or federated
Megaphone, the node ID is a hash of its public key, and the social networking platforms, multi-agent systems can play
couple of public/private keys is generated autonomously by an important role. Indeed, one of the very specific features
each node. of multi-agent systems is the sociality of agents, i.e., their
Messina et al. introduced HySoN [15], based on an overlay ability to communicate in a semantic way and to develop
network of software agents, which exploits a gossip protocol. trust relationships among them. Moreover, agents can (i)
HySoN allows users to locally maintain sensitive user’s data, express their communication acts by means of acknowledged
satisfying the privacy requirements preserving sensitive data. standards for interoperability among diverse systems, like
Indeed, the properties involved in the HySoN user aggregation FIPA; (ii) and exchange messages directly, in a peer-to-peer
are inferred by local data not published in the social network. way. Therefore, it is not surprising that these two technologies
Though some research works exist, for building a notifica- are often applied together for developing advanced social
tion system exploiting the Pastry DHT, very few works try platforms. In particular, multi-agent systems have been used as
to exploit the Kademlia DHT, which is used in BitTorrent (i) an underlying layer, or middleware, for developing social
and other content sharing systems, including the Blogracy networking platforms; and (ii) a technology to increase the
platform [8]. Matl et al. [16] deal with group communications autonomous and intelligent behavior of existing systems.
in overlay networks based on the Kademlia distributed hash For the first type of solutions, many of the distinguishing
tables (DHT), considering three cases: features of multi-agent systems can be fully exploited. Multi-
• Anycast, to deliver a message to any member of the agent systems provide semantic communication among agents,
group; which is handy for expressing all the different actions that
• Multicast, to deliver to all members; users can perform in a social platform. The different types of
• Manycast, to deliver to a particular subset of the group. messages can be understood according to their meaning and
The article describes some abstract solutions, based on tree applied according to existing trust relations among the users
structures built on top of the Kademlia layer. The advantages and their respective agents. In addition, complex negotiation
of these structures are better exploited if the branches are bal- protocols help creating acknowledgements and trust among
anced. Additional maintainance tasks are required to guarantee users, in an automatic or assisted way, without exposing
robustness and reliability, also in the case of frequent discon- sensitive data. Mobility can also be useful for moving the
nections of nodes. These tasks require periodical monitoring computation closer to data, if massive analysis is needed, but
of links and recovery mechanisms, for reconnecting the whole it can also be handy for adding functionality to a node of a
tree and avoiding loosing messages. distributed social platform or to a users client application.
With respect to the aforementioned approaches, our span- In the second case, agents are mainly used because of their
ning tree does not rely on a specific P2P architecture. More- proactive and reactive behaviors that can provide recommen-
over, it does not require that all nodes of the underlying dations of both users and content, and that can enable the
143
Workshop "From Objects to Agents" (WOA 2019)
personalization of results. Reactive abilities are particularly involved node. Higher values of this parameter lead to less
important in a social networking environment where events deep trees, but increase the number of messages to forward at
happen continuously and users can be easily distracted by each step.
the huge information flow, which is associated with highly
connected social networks [17]. Sensing the environment and A. Group Join
executing automatic tasks can reduce this overload signifi- A node that intends to join a group, and thus its associated
cantly. Goal-oriented behaviors, on the other hand, can support logical tree, has to find a node of the tree and send a
users in prosecuting their long term objectives about friend and join request to that node. There are various possibilities for
content discovery, i.e., to discover known persons registered performing both steps of the process. A connection point is
in the network, to make new acquaintances with users with a node to which a join request can be sent. We suppose that
common interests, to find interesting content hidden in less each node participating to a group, registers under the group
relevant data or from new sources. identifier into the P2P network. As described by Matl et al.
[16] with reference to the Kademlia network, it is possible for
B. Blogracy a new node to contact some other node, already in the group,
Blogracy [8] is a distributed social networking system which without finding and contacting the root node. In particular,
uses many of the services and techniques described above, we have defined the following two connection policies: (i)
with the aim to provide adaptive and composite services the join request is only sent to the root node (root strategy);
on top of its core features. At the lower level, Blogracy (ii) the join request is sent directly to the first node found,
uses widespread and stable peer-to-peer technologies, such which already participates to the tree (first strategy). In the
as distributed hash tables and the BitTorrent protocol, for first case, the join request is sent only after finding the root
coping with the intrinsic defects of centralized architectures node. Sending the request to the root node can lead to a more
and to become the basis of solid distributed social networking balanced tree, under some conditions. In the second case, the
platforms. At the higher level, it takes advantage of multi-agent join request is sent more easily as soon as any node of the
systems for simplifying the implementation of social network tree is found. In this way, the workload on the root node is
services in a decentralized setting. reduced, consequently removing a possible bottleneck.
The architecture of the application is modular and composed
B. Connection
of two basic components: (i) an underlying module for basic
file sharing and DHT operations, built as an extension of After a node n has been chosen as an entry point to the
existing implementations, and (ii) an OpenSocial container, group, a join request is sent to it, for being accepted as a
i.e., a module providing the services of the social platform new child node. Node n checks if it can accept one more
to the local user through a Web interface. Additionally, the child node, according to the node degree k of the tree (i.e.,
system supports autonomous agents for providing (i) recom- the maximum number of children each node may have). If
mendations of both users and content, (ii) personalization of the answer is positive, the connection is successful. Else, if n
results, and (iii) trust negotiation mechanisms. does not have room for one more child node, it is necessary to
The Blogracy system itself relies only on users nodes for its find another possible entry point. In fact, in its refusal answer,
operation and users need to perform background tasks on their n also inserts a reference to an alternative connection point,
own, in a distributed way. A layer of autonomous agents takes which is chosen among its own children. Simple possible
charge of assisting the user in finding new interesting content policies for this choice include: (i) the minimun XOR distance
and connections, and in pushing the local users activities to between the chosen node and the new one, similarly to the
followers. other protocols of a Kademlia network; or (ii) a random
selection, which may be a simplistic approach, but could
IV. D ESIGNED ALGORITHMS nevertheless provide surprisingly good results in some cases.
As demonstrated by the systems described is Section II, However, also the new connection point can be unavailable,
a practical approach for implementing distributed publish- thus the process goes on iteratively, till finding a suitable
subscribe systems is to organize a group of peers in a tree- connection point.
like structure. In this way, each node has the duty to forward Algorithms 1 and 2 illustrate the procedures for sending and
messages to a limited number of intermediate destination handling join requests, respectively.
nodes, which are directly linked to it. Section V will discuss
some guidelines for the organization and functioning of these Algorithm 1 Join request, followed by acceptance or refusal.
trees, obtained through simulations of various algorithms and Require: a ref erence to a node of the tree
configurations, which are introduced in this section. response = ref erence.ConnectionRequest()
Since P2P systems have to scale to a very large number of while not response.connectionAccepted() do
nodes, as a first feature to configure it is necessary to choose ref erence = response.getAlternativeN ode()
the degree of nodes, i.e., the maximum allowed number of response = ref erence.ConnectionRequest()
children nodes, for each parent node. The aim is to obtain the end while
best performance, without creating excessive burden for each
144
Workshop "From Objects to Agents" (WOA 2019)
Algorithm 2 Management of a join request. numChildren
represents the children count, maxChildren is the maximum
degree set for the tree.
Require: request f rom node n
Ensure: request response
if numChildren < maxChildren then
buildConnection()
numChildren = numChildren + 1
return ConnectionAccepted (a) (b)
else Fig. 1. Subtree breakout (a) and subtree preservation (b) algorithms. In subtree
response = ConnectionRef used breakout, nodes n2 ,n3 ,n4 ,n5 and n6 try to reconnect autonomously to the
response.setAlternativeN ode() tree, after n1 fails. In subtree preservation, the structures of subtrees below
n2 and n3 are unaltered after n1 fails.
return response
end if
in green and blue) remains unaltered till the new connection.
Only nodes n2 and n3 are involved in finding a new connection
C. Tree Reconstruction
point to the main tree.
Once the tree structure has been established, it is necessary The last recovery algorithm we propose is denoted as
to ensure its maintainance. In fact, in a P2P environment, each recursive election. The previous algorithms do not guarantee
element can suddenly disconnect or disappear. If a node of the to solve the problem of the disconnection of the root node.
tree fails, some mechanisms need to be in place to assure the This particular case can be solved with an election of a
reachability of all remaining nodes, including the children and substitute node among the former children of the disconnected
descentants of the failed node. root. This election can be performed efficiently with the bully
First of all, some mechanisms need to be adopted to peri- algorithm [18]. For the election, we have considered two
odically check connections. This can be enforced in practice different policies:
by sending periodical ping requests from each node to its own
direct neighbours. If a ping request is not answered before a • distance, the elected node is the one with the closest
timeout, the node has to be supposed to be missing. identifier to the group identifier, according to the XOR
A disconnection can lead to two fundamental problems. If a distance;
• lifetime, the elected node is the one which has been
leaf node disconnects, the problem is limited and it is sufficient
to remove its link with the parent node. Instead, if a node with connected for the longest time, thus coherently assigning
children diconnects, an additional problem is represented by a more important role to the more reliable and continuous
the reachability of the children and descendants; in fact, it is nodes.
necessary to reconnect all those nodes to the main tree, i.e., to To complete the election process, it is necessary that each
reconstruct the tree. To solve the problem of the reconstruction child maintains a reference to all its own siblings. Such
of a tree, we have devised various algorithms. references have to be kept fresh and constantly updated.
The subtree breakout algorithm is the simplest procedure, Once a new root node is elected, it takes charge of all its
from the logical point of view. It simply consists in assigning former siblings. Instead, its own previous children may have
to each node in the broken branch the duty to reconnect to to reconnect to the tree, if their parent node is no more able
the tree, individually. A node that finds its own parent to be to keep them, according to the maximum allowed degree for
disconnected, tells its children to find a new entry point. It then the tree.
removes all its own links and autonomously tries to reconnect For their reconnection, these nodes can break or maintain
to the tree. Each child and descendant acts in the same way, the structure of their own branch, according to one of the
till all nodes are reconnected. policies described above. However, an alternative solution
The subtree preservation algorithm is more conservative is to apply the same mechanism described to replace the
with respect to the broken branches, after their parent node root node, with an election among siblings according to the
disconnects. In fact, it is based on a mechanism of reconnec- bully algorithm. And similarly, this approach can be applied
tion, in which the topmost node is assigned the responsibility recursively at each level of the disconnected branch. In this
to reconnect to the main tree, possibly without affecting its case, each node, at each level of the structure, has to keep
descendants. references to all its own siblings. Moreover, since each node
Figure 1 shows the two cases. Case (a) represents the subtree could have to substitute its own parent, in case of being
breakout algorithm. Node n1 fails; the different colors of elected, it has to keep a reference to its parent and to the
the descendants of n1 indicate a fragmentation of the sub- node immediately above it, in the tree.
structure, after which each node reconnects autonomously. Figure 2 represents some executions of the recursive elec-
Case (b) is related to the subtree preservation algorithm. After tion algorithm after a node disconnects. To ease the represen-
node n1 fails, the structure of its former branches (colored tation, the node degree k is supposed to be 3.
145
Workshop "From Objects to Agents" (WOA 2019)
nodes A and B is defined as τ = τA + τB . Each node’s
contribution is a continuous random variable with uniform
distribution in the interval [τmin , τmax ]. In our simulations,
we adopted the following values: τmin = 10 [ms], τmax = 20
[ms]. We define the propagation delay π as the time that is
necessary for the message to reach all nodes in the tree.
A. Group Join
To analyze the group join strategies denoted as root and first,
illustrated in Section IV, we have compared the performance
indicators defined above, by taking into account different
values for the node degree k.
In a first group of simulations, whose results are illustrated
in Figure 3, a tree with 4000 nodes has been constructed using
the root strategy and k ∈ {2, 4, 8, 16, 32, 64}. Then, the same
experiment has been performed using the first strategy. For
each value of parameter k, the simulation has been repeated 10
times, with different pseudorandom number generation seeds.
Fig. 2. Executions of the recursive election algorithm. At time t0 the root
node r fails. Node n3 is elected as a substitute. At time t1 , node n3 is no more 16
available for its previous role and must be substitued. Node n4 is elected as 15
substitute. At time t2 , node n4 is no more available and node n7 substitutes 14
it. No election is required in this case. At time t3 , the structure is completely 13
reorganized, with all nodes connected. 12
11
10
9
8
δ
V. S IMULATIONS 7
6
To evaluate the proposed algorithms, we used DEUS, 5
general-purpose discrete event simulation environment [19], 4
3
which is available as open source [20]. DEUS enables the 2 first
simulation of large and highly dynamic networks, with the 1 root
0
desired detail level. DEUS is particularly suitable to study 0 8 16 24 32 40 48 56 64
P2P architectures, focusing on overlay protocols [21]–[23]. k
Tree construction algorithms are compared in terms of 22
• workload ditribution on network nodes, 20
• quickness, 18
• communication robustness. 16
To this purpose, the following performance indicators are 14
12
taken into account.
ν
10
1) Number of control messages ν.: Tree construction and
8
maintenance require that nodes exchange control messages.
6
In our simulations, each node has its own counter ν, which
4
is incremented by 1 every time a control message is delivered 2 first
to the node. In this way, it is possible to characterize the root
0
amount of network traffic both locally and globally. A large 0 8 16 24 32 40 48 56 64
total number of control messages implies high consumption of k
network bandwidth, and poor user experience due to delayed
tree construction and maintenance. Fig. 3. Tree depth δ (left) and number of control messages ν per node (right),
for increasing values of k, comparing the root and first strategies for group
2) Tree depth δ.: Tree depth, defined as the maximum join.
distance between the root node and any leaf node, is a very
important metric. Given two trees with N nodes each, but dif- The variation of number of requests and tree depth with
ferent depths δ1 < δ2 , the one with depth δ1 is more balanced respect to k is evident. The higher k, the higher the balancing
than the one with depth δ2 . Higher balancing is preferable, as of the tree and the efficience in terms of message traffic. It is
it means reduced total delays and better parallelism. also worth noting than this behavior is more accentuated with
3) Propagation delay π.: According to a widely used the first strategy. The root strategy produces slightly lower
approach [16], the communication delay between any two depth values, with respect to the first strategy, for any k value.
146
Workshop "From Objects to Agents" (WOA 2019)
Taking into account all these aspects, the first strategy is better We recall that for the strategy that imply node election after
than the root one. Thus, in the following, all presented results a root node failure, the XOR distance has been used as the
are those regarding the first strategy. winner selection metric. More specifically, the node with lower
In Figure 4, the propagation delay as a function of k distance is the one that gets selected.
is reported. Also for this performance indicator, the higher
variation is achieved for low k values, up to k = 8. Thus, TABLE II
considering all the performance indicators, the best tradeoff E FFECTS OF THE subtree breakout STRATEGY, FOR INCREASING VALUES OF
THE NODE DEGREE k. T HE FIRST ROW SHOWS THE δ AND ν VALUES
between performance and complexity is k = 8. BEFORE THE NODES FAIL .
% of failed nodes δ variation ν variation
400 - 6.0 - 7.1 -
1% 6.0 0% 7.5 4.3%
350 5% 5.9 -1.5% 9.4 31.1%
10% 5.8 -2.8% 11.5 60.9%
300 20% 5.8 -2.8% 15.6 117.3%
250 50% 5.4 -9.0% 37.9 427.9%
π
200
150 TABLE III
100 E FFECTS OF THE subtree preservation STRATEGY, FOR INCREASING
VALUES OF THE NODE DEGREE k. T HE FIRST ROW SHOWS THE δ AND ν
50 VALUES BEFORE THE NODES FAIL .
0 % of failed nodes δ variation ν variation
0 8 16 24 32 40 48 56 64
- 6.0 - 7.1 -
k
1% 6.4 8.1% 7.3 1.8%
5% 7.5 26.2% 7.6 6.1%
Fig. 4. Propagation delay π for increasing values of the node degree k, 10% 7.0 18.0% 8.1 13.7%
considering the first strategy for group join. 20% 8.1 36.0% 9.9 38.6%
50% 8.6 44.2% 18.9 163.7%
B. Connection
When a node receives a connection request, there may be TABLE IV
two different scenarios. In the first one, the node is able to E FFECTS OF THE recursive election STRATEGY, FOR INCREASING VALUES
OF THE NODE DEGREE k. T HE FIRST ROW SHOWS THE δ AND ν VALUES
accept a new child and acknowledges the connecting node.
BEFORE THE NODES FAIL .
In the second scenario, the node has already k children, thus
cannot accept a new one but can suggest another parent to the % of failed nodes δ variation ν variation
connecting node, according to either the distance or random - 6.0 - 7.1 -
1% 6.0 0% 7.2 1.3%
strategy (described in Section IV). 5% 6.0 0% 7.6 5.8%
To evaluate the performance of the aforementioned strate- 10% 6.0 0% 8.0 12.3%
gies, we performed 50 simulations for each one, considering 20% 6.0 0% 9.3 29.5%
50% 5.9 -1.6% 14.7 105.1%
the construction of a tree with 4000 nodes, with node degree
k = 8 and first strategy or group join. The results reported in
The results related to the subtree breakout strategy are
Table I show that the random connection strategy is slightly
illustrated in Table II. We can observe that tree depth remains
better that the distance one.
small even for the largest group of failed nodes. However,
TABLE I
the number of requests increases too much (427% when 50%
P ERFORMANCE EVALUATION OF THE CONNECTION STRATEGIES . nodes fail).
The results related to the subtree preservation strategy are
strategy δ ν
distance 6.93 7.68 presented in Table III. With respect to subtree breakout, the
random 6.00 7.20 tree depth increases considerably (by 44.26% in the worst
cade). The reason is that not breaking the tree may cause a
branch to be reconnected to a node that is already very deep
C. Tree Reconstruction in the tree. Fortunately, the increase of network traffic is lower
The strategies for tree reconstruction, illustrated in Section (163.7% in the worst case).
IV, are subtree breakout, subtree preservation and recursive The recursive election strategy is a compromise between
election. Their performance has been evaluated with respect to the previous ones. This is confirmed by the results reported
the disconnection of different groups of nodes, which are 1%, in Table IV. Facing a node group failure, tree depth slightly
5%, 10%, 20% and 50% of the total number of nodes in the changes and the number of requests has a very limited in-
tree, respectively. We considered a tree with 4000 nodes, k = crease. For these reasons, the recursive election strategy has
8, first group join strategy and random connection strategy. to be preferred.
147
Workshop "From Objects to Agents" (WOA 2019)
VI. C ONCLUSION [9] B. Guidi, A. Michienzi, and G. Rossetti, “Dynamic community analysis
in decentralized online social networks,” in Euro-Par 2017: Parallel
In this paper, we described and compared a number of Processing Workshops, 2017, pp. 517–528.
mechanisms for creating and managing a spanning tree, hosted [10] M. Amoretti, A. Ferrari, P. Fornacciari, M. Mordonini, F. Rosi, and
by a generic structured P2P network. The adopted decentraized M. Tomaiuolo, “Local-first algorithms for community detection,” in
approach is motivated by the need to solve issues about CEUR Workshop Proceedings 1748, KDWeb2016, 2016.
privacy, censorship and control of personal data in DOSNs. [11] M. Castro, P. Druschel, A. Kermarrec, and A. I. Rowstron, “Scribe: A
large-scale and decentralized application-level multicast infrastructure,”
According to our simulations, tree robustness is guaranteed IEEE Journal on Selected Areas in communications, vol. 20, no. 8, pp.
by the following mix of strategies: first for group join, random 1489–1499, 2002.
for connection, and recursive election for tree reconstruction [12] D. Sandler, A. Mislove, A. Post, and P. Druschel, “Feedtree: Sharing
in case of node failures. web micronews with peer-to-peer event notification,” in P2P Systems
IV, ser. Lecture Notes in Computer Science, vol. 340. Springer, 2005,
Regarding future work, we plan to implement the proposed pp. 141–151.
algorithms in the Blogracy platform [8] and test them over [13] T. Xu, Y. Chen, X. Fu, and P. Hui, “Twittering by cuckoo: decentralized
the PlanetLab facility. Furthermore, we plan to improve the and socio-aware online microblogging services,” in ACM SIGCOMM
agorithms by means of adaptive strategies, e.g., for online Computer Communication Review. ACM, 2010, pp. 473–474.
tuning of the node degree k. [14] T. Perfitt and B. Englert, “Megaphone: fault tolerant, scalable, and
trustworthy p2p microblogging,” in Internet and Web Applications and
R EFERENCES Services (ICIW), 2010 Fifth International Conference on. IEEE, 2010,
pp. 469–477.
[1] G. Angiani, P. Fornacciari, M. Mordonini, M. Tomaiuolo, and E. Iotti, [16] L. Matl, T. Cerny, and M. J. Donahoo, “Effective Manycast Messaging
“Models of participation in social networks,” in Social Media Perfor- for Kademlia Network,” in Proc. of the 30th Annual ACM Symposium
mance Evaluation and Success Measurements. IGI Global, 2016, pp. on Applied Computing (SAC ’15), 2015, pp. 646–652.
196–224.
[17] G. Lombardo, P. Fornacciari, M. Mordonini, M. Tomaiuolo, and
[2] E. Franchi, A. Poggi, and M. Tomaiuolo, “Social media for online
A. Poggi, “A multi-agent architecture for data analysis,” Future Internet,
collaboration in firms and organizations,” International Journal of In-
vol. 11, no. 2, 2019.
formation System Modeling and Design, vol. 7, no. 1, pp. 18–31, 2016.
[3] S. Shankland, “Facebook blocks contact exporting tool,” Retrieved [18] H. Garcia-Molina, “Elections in a distributed computer system,” IEEE
January 26, 2014, 2010. [Online]. Available: http://news.cnet.com/8301- Trans. on Computers, vol. C-31, no. 2, pp. 48–59, 1982.
30685 3-20076774-264/facebook-blocks-contact-exporting-tool/ [19] M. Amoretti, M. Picone, F. Zanichelli, and G. Ferrari, “Simulating
[4] T. Berners-Lee, “Long live the web,” Scientific American, mobile and distributed systems with DEUS and ns-3,” in Proc. of the
vol. 303, no. 6, pp. 80–85, 2010. [Online]. Available: 2013 International Conference on High Performance Computing and
http://www.scientificamerican.com/article.cfm?id=long-live-the-web Simulation (HPCS 2013), 2013, pp. 107–114.
[5] A. D. Salve, P. Mori, and L. Ricci, “A survey on privacy in decentralized
online social networks,” Computer Science Review, vol. 27, pp. 154–176, [20] M. Amoretti, “DEUS on GitHub,” cited June 2019. [Online]. Available:
2018. https://github.com/dsg-unipr/deus
[6] A. Poggi and M. Tomaiuolo, “A dht-based multi-agent system for [21] M. Martalò, M. Picone, M. Amoretti, G. Ferrari, and R. Raheli,
semantic information sharing,” Studies in Computational Intelligence, “Randomized network coding in distributed storage systems with layered
vol. 439, pp. 197–213, 2013. overlay,” in Proc. of the 2011 Information Theory and Applications
[7] B. Guidi, T. Amft, A. De Salve, K. Graffi, and L. Ricci, “DiDuSoNet: Workshop (ITA 2011), 2011, pp. 324–330.
A P2P architecture for distributed Dunbar-based social networks,” Peer- [22] M. Picone, M. Amoretti, and F. Zanichelli, “Evaluating the robustness of
to-Peer Networking and Applications, pp. 1–18, 2015. the DGT approach for smartphone-based vehicular networks,” in Proc.
[8] E. Franchi, A. Poggi, and M. Tomaiuolo, “Blogracy: A peer-to-peer of the 36th Annual IEEE Conference on Local Computer Networks (LCN
social network,” International Journal of Distributed Systems and Tech- 2011), 2011, pp. 820–826.
nologies (IJDST), vol. 7, no. 2, pp. 37–56, 2016.
[15] F. Messina, G. Pappalardo, D. Rosaci, C. Santoro, and G. Sarné, “Hyson: [23] M. Amoretti, A. L. Lafuente, and S. Sebastio, “A cooperative approach
A distributed agent-based protocol for group formation in online social for distributed task execution in autonomic clouds,” in Proc. of the
networks,” in Multiagent System Technologies (MATES 2013), Lecture 21st Euromicro International Conference on Parallel, Distributed, and
Notes in Computer Science, 2013, pp. 320–330. Network-Based Processing (PDP 2013), 2013, pp. 274–281.
148