-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 hwaitnhd,apdedeirti-oton-apleaerrcshyistteecmtusrcaalncoomveprlceoxmitey.thTehsies ipssaupeesr, idneesxccrhibaensgae 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. opprearraftoincryumlakerdi,ndbwyeofudseuesprcsdraiobtfee amanDedsisstacrogibmesuptfeaodrreOsdpnirflifenearedeinSntogcmisaoelccNihaaelntwaiscomtrivksi.tfiIoenrs vidIendtwhiisthpaapsepra,nwniengdetrseceribfoer sdpiestcriifibcuatilnlyg aonPli2nPe nsyostitfiemcatipornosthe 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. INTRODUCTION [10]. In particular, we describe and compare some mechanisms for the creation and management of the spanning tree. With respect to similar approaches, our spanning tree does not rely on a specific P2P architecture, and does not require that all nodes of the underlying P2P network are fully involved in the DOSN. Any structured P2P network (such as Chord, Kademlia, or Pastry) could be used as a substrate for several partially overlapping spanning trees, each one corresponding to a specific group of users. The manuscript is organized as follows. Section II analyzes the state of the art for P2P publish-subscribe systems. Section IV illustrates and proposes some algorithms for the creation and management of a tree structure among peers. Section V shows the results obtained by comparing the proposed different mechanisms and policies. Finally, some concluding remarks are provided in Section VI.
Social media attracts millions of people, who in fact spend
most of their online time social networking, for a variety
of everyday actions. Accordingly, these social platforms are
assuming different forms and aims, including distribution of
news, sharing of photos and videos, direct messaging, group
discussions, etc. [
In fact, even if the social networking systems are greatly
dissimilar in their user base and functionality [
Conversely, in exchange with additional architectural
complexity, peer-to-peer (P2P) systems essentially achieve
automatic resource scalability, in the sense that the availability of
resources is proportional to the number of users [
Castro et al. proposed Scribe [
distribution service based on P2P subscription mechanisms. FeedTree proposes a transition toward pushing RSS items over a P2P network, distributing the load over the nodes of a group multicast tree. For this purpose, FeedTree exploits Pastry and Scribe.
Xu et al. introduced Cuckoo [
Perfitt & Englert proposed Megaphone [
Messina et al. introduced HySoN [
Though some research works exist, for building a
notification system exploiting the Pastry DHT, very few works try
to exploit the Kademlia DHT, which is used in BitTorrent
and other content sharing systems, including the Blogracy
platform [
With respect to the aforementioned approaches, our spanning tree does not rely on a specific P2P architecture. Moreover, it does not require that all nodes of the underlying P2P network are fully involved in the DOSN. Structured P2P networks like Chord, Kademlia, or Pastry, could serve as a substrate for partially overlapping spanning trees, each one corresponding to a specific group of users. That is, one peer may belong to different groups at the same time.
The diffusion of online social networks is opening new scenarios for envisaging novel kinds of applications, either to support new social networking activities, or to exploit established relationships among users and use them to offer higherlevel services. Software agents are a natural fit for mediating access to local software- or hardware-based services, including access to data, sensors, monitors, printers and various kinds of actuators. Given their ability to negotiate and plan in a dynamic social context, software agents are also good for composing locally available services and resources, following existing trust relationships with other persons and agents located in the users proximity area. New trust relationships can also be created, on the basis of reputation and mutual acknowledgement, through the incremental and controlled exchange of profile data.
Especially in the case of completely distributed or federated social networking platforms, multi-agent systems can play an important role. Indeed, one of the very specific features of multi-agent systems is the sociality of agents, i.e., their ability to communicate in a semantic way and to develop trust relationships among them. Moreover, agents can (i) express their communication acts by means of acknowledged standards for interoperability among diverse systems, like FIPA; (ii) and exchange messages directly, in a peer-to-peer way. Therefore, it is not surprising that these two technologies are often applied together for developing advanced social platforms. In particular, multi-agent systems have been used as (i) an underlying layer, or middleware, for developing social networking platforms; and (ii) a technology to increase the autonomous and intelligent behavior of existing systems.
For the first type of solutions, many of the distinguishing features of multi-agent systems can be fully exploited. Multiagent systems provide semantic communication among agents, which is handy for expressing all the different actions that users can perform in a social platform. The different types of messages can be understood according to their meaning and applied according to existing trust relations among the users and their respective agents. In addition, complex negotiation protocols help creating acknowledgements and trust among users, in an automatic or assisted way, without exposing sensitive data. Mobility can also be useful for moving the computation closer to data, if massive analysis is needed, but it can also be handy for adding functionality to a node of a distributed social platform or to a users client application.
In the second case, agents are mainly used because of their
proactive and reactive behaviors that can provide
recommendations of both users and content, and that can enable the
personalization of results. Reactive abilities are particularly
important in a social networking environment where events
happen continuously and users can be easily distracted by
the huge information flow, which is associated with highly
connected social networks [
Blogracy [
The architecture of the application is modular and composed of two basic components: (i) an underlying module for basic file sharing and DHT operations, built as an extension of existing implementations, and (ii) an OpenSocial container, i.e., a module providing the services of the social platform to the local user through a Web interface. Additionally, the system supports autonomous agents for providing (i) recommendations of both users and content, (ii) personalization of results, and (iii) trust negotiation mechanisms.
The Blogracy system itself relies only on users nodes for its operation and users need to perform background tasks on their own, in a distributed way. A layer of autonomous agents takes charge of assisting the user in finding new interesting content and connections, and in pushing the local users activities to followers.
As demonstrated by the systems described is Section II, a practical approach for implementing distributed publishsubscribe systems is to organize a group of peers in a treelike structure. In this way, each node has the duty to forward messages to a limited number of intermediate destination nodes, which are directly linked to it. Section V will discuss some guidelines for the organization and functioning of these trees, obtained through simulations of various algorithms and configurations, which are introduced in this section.
Since P2P systems have to scale to a very large number of nodes, as a first feature to configure it is necessary to choose the degree of nodes, i.e., the maximum allowed number of children nodes, for each parent node. The aim is to obtain the best performance, without creating excessive burden for each involved node. Higher values of this parameter lead to less deep trees, but increase the number of messages to forward at each step.
A node that intends to join a group, and thus its associated
logical tree, has to find a node of the tree and send a
join request to that node. There are various possibilities for
performing both steps of the process. A connection point is
a node to which a join request can be sent. We suppose that
each node participating to a group, registers under the group
identifier into the P2P network. As described by Matl et al.
[
After a node n has been chosen as an entry point to the group, a join request is sent to it, for being accepted as a new child node. Node n checks if it can accept one more child node, according to the node degree k of the tree (i.e., the maximum number of children each node may have). If the answer is positive, the connection is successful. Else, if n does not have room for one more child node, it is necessary to find another possible entry point. In fact, in its refusal answer, n also inserts a reference to an alternative connection point, which is chosen among its own children. Simple possible policies for this choice include: (i) the minimun XOR distance between the chosen node and the new one, similarly to the other protocols of a Kademlia network; or (ii) a random selection, which may be a simplistic approach, but could nevertheless provide surprisingly good results in some cases. However, also the new connection point can be unavailable, thus the process goes on iteratively, till finding a suitable connection point.
Algorithms 1 and 2 illustrate the procedures for sending and handling join requests, respectively.
Algorithm 1 Join request, followed by acceptance or refusal. Require: a ref erence to a node of the tree response = ref erence.ConnectionRequest() while not response.connectionAccepted() do ref erence = response.getAlternativeN ode() response = ref erence.ConnectionRequest() end while 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 else response = ConnectionRef used response.setAlternativeN ode() return response end if (a) (b) in green and blue) remains unaltered till the new connection. Only nodes n2 and n3 are involved in finding a new connection point to the main tree.
The last recovery algorithm we propose is denoted as
recursive election. The previous algorithms do not guarantee
to solve the problem of the disconnection of the root node.
This particular case can be solved with an election of a
substitute node among the former children of the disconnected
root. This election can be performed efficiently with the bully
algorithm [
to ensure its maintainance. In fact, in a P2P environment, each element can suddenly disconnect or disappear. If a node of the tree fails, some mechanisms need to be in place to assure the reachability of all remaining nodes, including the children and descentants of the failed node.
First of all, some mechanisms need to be adopted to periodically check connections. This can be enforced in practice 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; leaf node disconnects, the problem is limited and it is sufficient • lifetime, the elected node is the one which has been 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 elecCase (b) is related to the subtree preservation algorithm. After tion algorithm after a node disconnects. To ease the represennode n1 fails, the structure of its former branches (colored tation, the node degree k is supposed to be 3. 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.
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 available for its previous role and must be substitued. Node n4 is elected as substitute. At time t2, node n4 is no more available and node n7 substitutes it. No election is required in this case. At time t3, the structure is completely reorganized, with all nodes connected.
general-purpose discrete event simulation environment [
Tree construction algorithms are compared in terms of • workload ditribution on network nodes, • quickness, • communication robustness.
To this purpose, the following performance indicators are taken into account.
maintenance require that nodes exchange control messages. In our simulations, each node has its own counter ν, which is incremented by 1 every time a control message is delivered to the node. In this way, it is possible to characterize the amount of network traffic both locally and globally. A large total number of control messages implies high consumption of network bandwidth, and poor user experience due to delayed tree construction and maintenance.
2) Tree depth δ.: Tree depth, defined as the maximum distance between the root node and any leaf node, is a very important metric. Given two trees with N nodes each, but different depths δ1 < δ2, the one with depth δ1 is more balanced than the one with depth δ2. Higher balancing is preferable, as it means reduced total delays and better parallelism.
3) Propagation delay π.: According to a widely used
approach [
The variation of number of requests and tree depth with respect to k is evident. The higher k, the higher the balancing of the tree and the efficience in terms of message traffic. It is also worth noting than this behavior is more accentuated with the first strategy. The root strategy produces slightly lower depth values, with respect to the first strategy, for any k value. Taking into account all these aspects, the first strategy is better than the root one. Thus, in the following, all presented results are those regarding the first strategy.
In Figure 4, the propagation delay as a function of k is reported. Also for this performance indicator, the higher variation is achieved for low k values, up to k = 8. Thus, considering all the performance indicators, the best tradeoff between performance and complexity is k = 8.
We recall that for the strategy that imply node election after a root node failure, the XOR distance has been used as the winner selection metric. More specifically, the node with lower distance is the one that gets selected.
When a node receives a connection request, there may be two different scenarios. In the first one, the node is able to accept a new child and acknowledges the connecting node. In the second scenario, the node has already k children, thus cannot accept a new one but can suggest another parent to the connecting node, according to either the distance or random strategy (described in Section IV).
To evaluate the performance of the aforementioned strategies, we performed 50 simulations for each one, considering the construction of a tree with 4000 nodes, with node degree k = 8 and first strategy or group join. The results reported in Table I show that the random connection strategy is slightly better that the distance one.
illustrated in Table II. We can observe that tree depth remains small even for the largest group of failed nodes. However,
TABLE I the number of requests increases too much (427% when 50% PERFORMANCE EVALUATION OF THE CONNECTION STRATEGIES. nodes fail).
sdtirsatatengcye 6.δ93 7.ν68 preTsheneteredsuinltsTraebllaeteIdIIt.oWthiteh sruebstpreecet ptroesseurbvtaretieonbrsetaraktoeugty, tahree 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 intree, 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.
mechanisms for creating and managing a spanning tree, hosted by a generic structured P2P network. The adopted decentraized approach is motivated by the need to solve issues about privacy, censorship and control of personal data in DOSNs.
According to our simulations, tree robustness is guaranteed by the following mix of strategies: first for group join, random for connection, and recursive election for tree reconstruction in case of node failures.
Regarding future work, we plan to implement the proposed
algorithms in the Blogracy platform [