Communication Channel Management for Maintenance of Strong Overlay
Connectivity
∗Roberto B
ALDONISirio S
CIPIONISara T
UCCI-P
IERGIOVANNIDIS, Universit´a di Roma La Sapienza, Via Salaria 113, Roma, Italia.
baldoni,scipioni,tucci@dis.uniroma1.it
Abstract
A fundamental problem for both structured and unstruc- tured peer-to-peer networks is how to maintain connected the topology of a network in the presence of processes that, possibly concurrently, join and leave the network.
In this paper we firstly define a model of the computa- tion well-suited to analyze connectivity maintenance among processes carrying out a distributed computation consider- ing unbounded concurrency and infinite participation. Sec- ondly upon this model we provide a specification of the con- nectivity maintenance problem. We finally present a proto- col that guarantees connectivity maintenance by arranging processes of the computation on a tree. The protocol han- dles both joins and leaves concurrently and actively (i.e., some piece of code is executed by a leaving/joining process interacting with its neighbors in the topology).
1. Introduction
One of the main characteristics of a peer-to-peer (P2P) system is its ability to handle membership changes while keeping operative its nice basic functions used by appli- cations. Membership changes occur when peers join and leave the P2P system, possibly concurrently, at any arbi- trary time. Generally speaking, in a P2P system peers are connected through an overlay network and its set of con- nections form the communication topology of the P2P sys- tem. P2P systems can be indeed split in structured (e.g., [13, 14, 16]) and unstructured (e.g., [4, 3, 6]) according to the fact if they have a stringent requirement to keep a pre- defined topology or not [7]. In a P2P structured system pro- cesses of the network collectively have to form a certain ideal topology (e.g., a ring in Chord [14]) despite member-
∗The work described in this paper was partially supported by the Italian Ministry of Education, University, and Research (MIUR) under the IS- MANET project and by the EU Project Resist
ship changes, this is to simplify the mapping between the physical (process) space and the abstract space provided by the structured P2P network (e.g., the circular key space of Chord). Unstructured P2P systems topologies target ideal networks with constant degree and low diameter to guaran- tee short query path length and low control message over- head [12]. Maintaining either an ideal predefined topol- ogy or a topology with some structural properties requires keeping the connectivity of the topology (otherwise the P2P system simply does not work or it performs poorly).
Connectivity maintenance can be obtained through two general approaches: the passive approach and the active ap- proach. In the active approach a joining (resp., leaving) pro- cess executes some protocol to update the neighbor vari- ables. In the passive approach a repair protocol runs in the background to keep connectivity. In such an approach leaves are handled as fail-stop failures. As remarked in [7], there could be some hybrid approach which handle joins and leaves differently (e.g., passive join and passive leave [8], active join and passive leave [9, 5], active join and ac- tive leave [1, 7, 10]). Passive and active approach have ad- vantages and drawbacks. Passive approaches require con- siderable background network traffic due to the repair pro- tocol while keeping simple the protocol of a process by con- sidering leaves as fail-stop failures. The active approach does not add network traffic, just a few messages exchanged between a joining/leaving process and its neighbors, never- theless it brings to complex protocols handling joins and leaves which are difficult to design and to prove its formal correctness.
This paper addresses the problem of connectivity main- tenance of the communication topology behind a distributed computation in a very general computational model de- scribed in Section 2. In this model (i) processes are free to join and leave the distributed computation when they wish, (ii) the admitted level of participation is infinite (i.e., an in- finite number of processes can eventually join the computa- tion), (iii) the admitted level of concurrency, defined as the number of processes forming the distributed computation at
any given time, is unbounded [11] and, due to infinite partic- ipation, (iv) each process has a partial view of the processes belonging to the system.
After defined the computational model, we provide in Section 3 a specification of the active connectivity mainte- nance problem. This specification states that all processes participating the distributed computation are the vertices of a connected communication topology along the time.
Specifically, it implies that when a process p joins the com- putation, it must be connected to each other process belong- ing to this set through either a direct or a sequence of com- munication channels. Secondly, each process p belonging to the set of processes forming the distributed computation should remain ever connected over the time to any other other member of this set despite membership changes till p leaves. Finally, the active connectivity maintenance speci- fication endows a liveness property that crystallizes the dif- ficulty for a process to join a set of processes constantly changing in its membership. In other words, the difficulty for a process wishing to participate to the computation to establish a communication channel with one of the pro- cesses involved in the computation. This is due to the in- finite participation, the continuous arrivals and departures of processes, and to the asynchrony of the underlying com- munication system.
Hence, we present a protocol along with its correctness proof that follows an active approach for joins and leaves to guarantee active connectivity maintenance. This protocol arranges processes forming the distributed computation on a tree.
To the best of our knowledge only one paper [7] has ad- dressed a similar issue. Specifically [7] studied the problem of active maintenance of a specific topology (i.e., a ring) in a structured P2P system with bounded concurrency and finite participation. Our results are therefore obtained in a weaker setting (infinite participation and unbounded concurrency) than the one proposed in [7] and are referring to a weaker property, namely active connectivity maintenance, than the active maintenance of a ring. Let us remark that providing protocols handling infinitely many processes matches re- quirements of any P2P system where the number processes involved in the P2P system along the time can potentially be infinite.
2. Model of the Computation
The system is composed by a infinite set of processes Π. Processes communicate only by exchanging messages, message delays and process scheduling delays are un- bounded, and there is no global clock. To simplify the de- scription without losing generality, we assume the existence of a fictional global clock, whose output is the set of positive integers denoted byT .
Let us describe a run of a process p ∈ Π. Initially p is inactive. An inactive process is out of the distributed com- putation. At any time t, p may become active trying to join the distributed computation. At any time t > t, the active process p may become inactive. An active process that re- mains active forever is called a stable process. An active process that becomes inactive at a give time is called a tran- sitory process. We denote as A(t) the set of active processes at time t.
The admitted level of concurrency, i.e. the maximum number of processes that may be active simultaneously, is unbounded. This means that at any time t the number of processes that are simultaneously active is finite but can grow without bound [11]. Thus, at any point of time t∈ T the set A(t) is finite but the number of concurrently active processes is unknown.
The admitted level of participation is infinite, i.e., infi- nite processes can eventually become active. However, once a process p becomes inactive it remains inactive forever.
This assumption is not restrictive as a process can partic- ipate to the distributed computation with another identifier an infinite number of times thanks to the infinite nature of Π. Infinite participation implies that there is no assumption on eventual stable components since the set of concurrently active processes may change infinitely often, i.e. there is no point of time t∈ T after which A(t) = A(t) for each t> t.
Process Local View. Due to the infinite nature of Π, each process p ∈ Π in the system is associated with a partial and finite subset of Π, constituting its local view of the system. p starts its run at time t0 with an ini- tial knowledge of other processes given by the local view p.lvt0. Then, p may acquire new knowledge on pro- cesses of the system installing new views. This knowl- edge could be gained either through interactions with other processes or external ”ad-hoc” services. Therefore, each process p install a sequence of views at successive instants of time{p.lvt0, p.lvt1, . . . p.lvti, p.lvti+1,...p.lvtm} and the local view of p at time t, p.lvt = p.lvti if and only if t∈ [ti, ti+1).
Communication Channels. Processes exchange mes- sages through reliable channels that must be explicitly es- tablished. To establish a communication channel at time t between p and q is necessary that p∈ q.lvt(or q ∈ p.lvt).
In practice this necessary condition has to be true for a time long enough to allow the set up of the communication channel and to take into account the message transfer delay.
Once established, two processes p, q exchange messages in a bidirectional way.
Connectivity between two processes. Two processes are directly connected if there exists a communication channel between them. Even if two processes p, q are not directly connected they can communicate if there exists a transitive connection, i.e., there exists a sequence of communication channels between them. In the following, whenever not necessary, we do not specify if two processes are connected in a direct or transitive way, but we say that they are simply connected (or enjoy connectivity). Connectivity between two processes is not a stable relation in a dynamic system, it may change along the time. For this reason, we formally define the relation of connectivity between two processes as a function of time t, denoted as↔t, as follows:
Definition 1 (Connectivity between two processes). p ↔t
q with p = q if and only if p, q ∈ A(t) and one of the following conditions holds at time t:
1. there exists a communication channel between p and q at time t (direct connection);
2. ∃r s.t. p ↔trand r↔tq.
Processes of the Distributed Computation. If a process is active, it does not mean that it has already established or it will establish a communication channel with another active process (consider the case when the local view of an active process never contain active processes). We denote as joinp
the event through which the process p establishes its first connection, while leavep defines the event through which p closes all its connections previously established. After leavepthe process never establishes other connections1.
Let us denote as C(t) the set of pairs p, p.Channels
constituted by each process p previously joined but not yet left along with the set p.Channels comprising all direct connections(p, q) between p and q at time t.
The set C(t) actually represents the set of processes par- ticipating to the distributed computation at time t and the set of communication channels between the members of C(t), i.e. C(t) forms the communication topology of the distributed computation at time t2.
2.1. Active Connectivity Maintenance Specification
The active connectivity maintenance specification is bro- ken in two properties: a Safety property and a Liveness property. Specifically the Safety property states that the communication topology C(t) must be always connected
1This is not a constraint, as any process can join again with another identifier infinite times thanks to the infinite nature ofΠ.
2In the reminder of the paper, whenp belongs to a pair of C(t), we shortly writep ∈ C(t).
along the time, i.e. there exists (direct or transitive) con- nectivity between any pair of processes belonging to C(t) at each point of the time despite process leaves. The Live- ness property states that any active process wishes to join, eventually succeeds in doing so. Formally,
Property 1 (Safety). At any time t,∀p, q :
p, p.Channels, q, q.Channels ∈ C(t) ⇒ (p ↔tq) Property 2 (Liveness). Let p ∈ A(t) a process that be- comes active a time t. If there exists a C(t), t ≥ 0, con- taining at least one stable process, then there exists a time t> t in which p∈ C(t).
It is worth to note that the Liveness property does not guarantee that an active process (even if a stable one) will be eventually a member of C(t). This fact derives from the im- possibility to establish a connection in a concurrent system with infinite participation if eventually either at least one stable participant does not become member of C(t) or at least one transitory process does not remain active enough time to allow a newcomer to join. In fact the infinite race be- tween a continuously changing set of (transitory) processes belonging to the distributed computation and the local views of an active process could either have a null intersection for any t or the intersection could be non null for a period of time not long enough to physically establish a communica- tion channel.
3 A Protocol ensuring Active Connectivity
Maintenance
We propose a protocol that maintains active connectivity among processes belonging to the distributed computation.
This protocol arranges such processes on a routed tree com- munication topology. The protocol maintains such a topol- ogy despite leaves and joins by using an active approach (i.e., a piece of code is executed by a leving/joining process interacting with its neighbors in the topology).
3.1 Data Structures and Communication Primitives
Process States. Each process p has a variable state that can assume the values{in, inactive, joining, leaving}.
Initially the variable assumes the inactive value.
• p.state = joining, means that the active process p is trying to establish a communication channel with a process belonging to the tree (i.e., a process with state = in, see below).
• p.state = in means that p is a connected process, i.e. it belongs to the tree. The transition joining → in at time t represents the p’s join event a time t.
• p.state = leaving means that p is working to build
repairing connections before tearing down all own commu- nication channels.
• When p.state = inactive, p has no established com- munication channel with other processes. The transition leaving → inactive at time t, represents the ps leave event at time t.
Local Views.
External Views. We suppose that local views for each pro- cess p that does not yet belong to the tree (p.state = joining) are delivered by a local view service. To ensure the Liveness Property, i.e. to assure that an active process eventually joins, the local view service service has to satisfy the following property3:
Property 3. If the tree eventually comprises a vertex that is a stable process p, the local view service eventually delivers to any process a view including a stable process in the tree4. Let us remark that without Property 3, under infinite participation and unbounded concurrency (see Section 3), an active process may suffer starvation, i.e it may never join the tree.
Internal Views. Each process p, once joins the tree, sub- stitutes the external view with an internal view structured in two sets: p.parent and p.children. p.parent and p.children are initialized to ∅. Successive values are ob- tained by interacting with processes belonging to the tree.
We assume that the tree is initiated by one process with an empty local view. Formally:
Assumption 1. The tree is initiated at time t0 by a root process r through a virtual joinr such that r.state = in and no established communication channel, i.e., C(t0) = (r, ∅)
Primitives for Communication Channels. To establish a communication channel two primitives are exploited: con- nect(q,type) and accept(q, type).
The connect(q, type) primitive is invoked by a process p that wants to establish a communication channel with a pro- cess q. The parameter type indicates the (direct) connection type. When the connect(q, type) returns the communication channel has been established.
The process p accepts a connection of type type previ- ously invoked by q through an accept(q, type) primitive.
3Practically, it is sufficient that the service delivers a processq belong- ing to the distributed computation during a finite time interval long enough for establishing a communication channel withq.
4This property can be implemented in a very easy way considering, for example, each process in the group sends regularly heartbeats to this service in order to witness its presence in the group and the service includes in a view some of the “oldest” processes. Also, star-shaped topologies can be avoided by using some strategies ensuring a diversification of local views, e.g. based on proximity information.
A process p closes the connection with another process q with a close(q) primitive. A process p closes all previously established communication channels with close().
Once a communication channel between p and q is estab- lished, p and q exchange messages through send()/ receive() primitives.
3.2 Protocol Behavior
Each process p endows a Connectivity Module to main- tain a routed tree topology. The connectivity module and p communicate through the variable state. As soon as an active process wishes to join it sets its state to joining.
Any process on the tree wishing to leave sets its state to leaving. The actual occurrence of the join and leave event is managed by the Connectivity Module, i.e. the Connectiv- ity Module manages the state transitions: joining → in and leaving → inactive.
To guarantee Active Connectivity Maintenance, the state transition joining → in does not pose any problem as it does not threat the connectivity of participants. The critical transition is leaving → inactive, since in the tree topol- ogy each leave, but the one executed by a leaf, creates a partition. Then, before a process p becomes inactive, the local view of p is communicated to its neighbors (the par- ent). Basing on this new local view, the children and the parent of the leaving node are able to establish new commu- nication channels connecting them. This allows to maintain connectivity among participants. Note also the need of cop- ing with two (or more) concurrent leaving processes which are adjacent on a same path. In this case an order on the de- parture of these conflicting leaving processes is needed and it is given by the direction of the edge. The process closest to the root leaves first.
The Connectivity Module. In Figure 1 the pseudo-code of the Connectivity Module is shown.
joining→ in transition. When the state variable p.state assumes the joining value, the Connectivity Module es- tablishes exactly one communication channel between p and one process q (lines 1,2) using the currently installed local view lvt provided by the the local view service5. Note that, the channel is established with a process q with q.state= in (line 15, 17-18). Moreover, once the commu- nication channel has established p.parent= q (line 3) and p∈ q.children (line 18). Then, the variable p.state is set to in (line 3) when p becomes a leaf of the tree.
5To implement this step, processp could scan sequentially lvtpro- vided by the local view service till a connection has been established. For the sake of clarity of the pseudo-code, this part is not shown in the code.
Interestingly the property provided by this part of code is similar to the one provided by the contact() function used in [7].
1 when(state = joining) do
2 wait until(∃! q ∈ lvt: connect(q, joining)) 3 parent:= q; state = in;
4 when(state = leaving) do
5 do
6 parent change:= ⊥;
7 send[“LEAVE”(children)] to parent;
8 wait until(receive [“ACK LEAVE”] from parent);
9 while(parent change) 10 close(); state := inactive
11 when((receive [“LEAVE”(newchildren)] from q ∈ children)∧
12 ∧(state = in)) do
13 children:= childrenSnewchildren− {q};
14 connect(q, in)∀q ∈ newchildren;
15 send[“ACK LEAVE”] to q;
16 while(state = {joining, inactive}) do 17 accept(q, type);
18 switch type
19 case joining: if (state = in)
20 then children:= childrenS
{q};
21 else close(q)
22 case in: parent := q; parent change = ;
Figure 1. The Pseudo-code of the Connectiv- ity Module at p
leaving → inactive transition. When the state variable p.state assumes the leaving value, the Connectivity Mod- ule repairs the tree with respect to the leave of p (lines 4-9), in order to satisfy Safety. Actually it ensures that the parent of p establishes a communication channel with each child of p.
In particular, the module executes a sequence of basic steps, and terminates when a basic step succeeds (line 9).
During each step, a “LEAVE” message containing the cur- rent children of p is sent to update the view of the p’s parent (line 7).
In the simple case where the p’s parent is in when the “LEAVE” message is received, it updates their chil- dren (line 12) variable, and establishes new communication channels with each new child (line 12). After line 12 is ex- ecuted, each new child has a communication channel estab- lished with p’s parent and the parent variable updated to p’s parent (line 20 ). At line 13, the p’s parent replies to p with an “ACK LEAVE” message. When this acknowledgment arrives at p, p leaves (line 10).
In a more difficult case, the p’s parent is leaving when the “LEAVE” message is received. In that case an order on the departures of p and its parent q is needed, to break the tie. The rule is the following: if p and its parent q have concurrent leaves, q leaves the system before p. In this case, while a step is running for p, a basic step succeeds for q.
Then a new channel is established between p and the q’s parent and p will have to start a new step (line 5–9) since the variable parent change has been set to true (line 20).
In the worst case scenario all ancestors of p are leaving processes. In this case the tree root is also involved in a leave, and thus a new root has to be found.
This can be done by considering an execution of a level- order traversal algorithm launched by the root whose aim is to return the first process whose state is in (if any). By the fact that a leaving process does not accept connections from new children (line 17 and 19) and by finite (even though un- bounded) concurrency, the level-order traversal algorithm execution eventually terminates. It is worth to note that if all processes in the tree are simultaneously leaving, the level- order traversal algorithm terminates but a live-lock arises since a new root has not been found. In this case different strategies may be pursued, e.g. the root could unblock all leaving processes in an arbitrary order and could switch to in waiting for a new child before trying to leave again6.
For sake of simplicity we consider only the case where the root is a stable process avoiding to consider the level- order traversal algorithm. In this case the number of steps, before p ends successfully a basic step (at line 9), is bounded by its depth in the tree.
4 Related Work
A few protocols following an active approach for joins and leaves have appeared in the literature [1, 7, 10] As ex- plained in the Introduction, the work of Li-Misra-Plaxton [7] is closely related to ours. The authors give a protocol to actively maintaining a ring of a structured P2P system on a system model allowing a fixed and finite number of processes and they used an assertional method to rigorously prove the correctness of their protocol. Our work differs from them in several points. Connectivity maintenance is a basic property that can be applied to structured and un- structured P2P systems. Secondly, our protocol is given on a more general setting, infinite participation and unbounded concurrency, than the one proposed in [7]. Thirdly, both protocols require an external service that delivers a view with a process belonging to the P2P system (Property 1), otherwise a process risks to starve without joining ever the P2P system.
As far as unstructured P2P systems is concerned, [12]
points out the importance of maintaining the network topol- ogy connected in such a setting for efficient searching. The target of [12] is to construct a random graph with low diam- eter O(logN) and limited process degree under a probabilis- tic model of process arrival and departure. Authors prove, among the others, that their protocol has the following prop- erty: when time t is enough bigger, the random topology is connected with probability close to one.
6If the root also leaves after the unblocking of the leaving processes the tree would become empty preventing successive joins.
Finally, while in this paper we analyze the process of continuous arrival and departure of processes (or churn), through a theoretical framework, this problem has been also studied recently from an analytical and performance view- point [8, 15]. Liben-Nowell et al. [8] has given a analysis of structured peer to peer networks operating in the face of concurrent joins and unexpected departures. They define a metric, half-life of the network, which essentially measures the time for replacement of half the nodes in the network by new arrivals. Using this metric they investigated the band- width consumed by topology repairing protocols and show that Chord is nearly optimal in this regard. Stutzbach and Rejaie in [15] have tried to explain the dynamics of P2P network systems or the dynamics of peer participation in terms of churn. They have characterized churn in Gnutella Network based on the fine-grained monitoring of the en- tire population. They have observed that the behavior of arrival and departure follows a power-law distribution, con- tradicting previous studies assuming a poisson distribution of arrivals and an exponential distribution of departures.
5 Concluding Remarks
We have shown in this paper: (i) a generic system model for capturing connectivity of a P2P system (both struc- tured and unstructured) with infinitely many processes; (ii) a specification of the active connectivity maintenance prob- lem and (iii) a protocol that satisfies the previous specifi- cation by maintaining a tree topology under both process joins and leaves. Many points need further research. As an example, it would be interesting to see if the specification of active connectivity maintenance is the weakest one that can be ensured on-the-fly in the system model of Section 2. Moreover, active approaches seem to be well-suited to include in the join/leave code some sort of incentive mech- anism typical of economic and game theories, to improve collaboration among peers to create an economy of equilib- rium.
References
[1] J. Aspnes and G. Shah. Skip graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 384-393, January 2003.
[2] Roberto Baldoni, Sara Tucci Piergiovanni: Group Membership for Peer-to-Peer Communication, Technical Report 2005, avail- able on http://www.dis.uniroma1.it/ midlab/publications [3] Bittorrent. [Online]. Available: http://bitconjurer.org/BitTorrent/
[4] Gnutella development forum, the gnutella v0.6 protocol. [On- line]. Available: http://groups.yahoo.com/group/the gdf/files/
[5] K. Hildrum, J. Kubiatowicz, S. Rao, and B. Y. Zhao. Distributed data location in a dynamic network. In Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architec- tures, pages 41-52, August 2002.
[6] Kazaa media desktop. [Online]. Available: http://www.kazaa.
com/
[7] X. Li, J. Misra, and C. G. Plaxton. Active and Concurrent Topol- ogy Maintenance. In Proceedings of the 18th International Sym- posium on Distributed Computing, pages 320-334, 2004. Ex- tended version Technical Report TR-04-21, Department of Com- puter Science, University of Texas at Austin, May 2004.
[8] D. Liben-Nowell, H. Balakrishnan, and D. Karger. Analysis of the evolution of peer-to-peer systems. In Proceedings of the 21st ACM Symposium on Principles of Distributed Computing, pages 233-242, July 2002.
[9] H. Liu and S. S. Lam. Neighbor table construction and update in a dynamic peer- to-peer network. In Proceedings of the 23rd International Conference on Distributed Computing Systems, pages 509-519, May 2003.
[10] N. Lynch, D. Malkhi, and D. Ratajczak. Atomic data access in content addressable networks. In Proceedings of the 1st In- ternational Workshop on Peer-to-Peer Systems, pages 295-305, March 2002
[11] Michael Merritt, Gadi Taubenfeld. Computing with Infinitely Many Processes. In Proceedings of the 14th International Sym- posium on Distributed Computing, pages 164-178, 2000.
[12] G. Pandurangan, P. Raghavan, and E. Upfal. Building low- diameter peer-to-peer networks. IEEE Journal on Selected Areas in Communications, 21:995-1002, August 2003.
[13] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, A scalable content addressable network, in Processings of the ACM SIGCOMM, 2001, pp. 161172.
[14] I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for Internet appli- cations. IEEE/ACM Transac- tions on Networking, 11:17-32, February 2003.
[15] Daniel Stutzbach, Reza Rejaie, Towards a Better Understanding of Churn in Peer-to-Peer Networks.Technical Report CIS-TR- 04-06, Department of Computer Science, University of Oregon, November, 2004
[16] B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz, Tapestry: A resilient global-scale over- lay for service deployment, IEEE Journal on Selected Areas in Communications, vol. 22, no. 1, pp. 4153, January 2004.
