Fast Construction of Overlay Networks Dana Angluin James Aspnes Jiang Chen Dept.Comp.Sci Dept.Comp.Sci Dept.Comp.Sci Yale University Yale University Yale University New Haven,CT 06520 New Haven,CT 06520 New Haven,CT 06520 dana.angluin@yale.edu aspnes@cs.yale.edu jiang.chen@yale.edu Yinghua Wu Yitong Yin Dept.Comp.Sci. Dept.Comp.Sci. Yale University Yale University New Haven,CT 06520 New Haven,CT 06520 y.wu@yale.edu yitong.yin@yale.edu ABSTRACT General Terms An asynchronous algorithm is described for rapidly con- Algorithms Theory structing an overlay network in a peer-to-peer system where all nodes can in principle communicate with each other di- rectly through an underlying network,but each participat- Keywords ing node initially has pointers to only a handful of other Overlay networks,asynchronous,merging,Patricia trees participants.The output of the mechanism is a linked list of all participants sorted by their identifiers,which can be used as a foundation for building various linear overlay net- 1 INTRODUCTION works such as Chord or skip graphs.Assuming the initial Consider the problem of rapidly building a peer-to-peer pointer graph is weakly-connected with maximum degree d system with a ring or line structure such as Chord [19]or and the length of a node identifier is W,the mechanism skip graphs 3.The default assumption in both systems ap- constructs a binary search tree of nodes of depth O(W)in pears to be that nodes will be inserted sequentially,giving expected O(W log n)time using expected O((d+W)nlogn) a construction time of O(nlog-n)for Chord and O(nlog n) messages of size O(W)each.Furthermore,the algorithm for skip graphs.But how quickly can we build such a sys has low contention:at any time there are only O(d)unde- tem if we do so in parallel,assuming that initially each node livered messages for any given recipient.A lower bound of only knows about a few other nodes in the system?At min- (d+log n)is given for the running time of any procedure imum,we need to be able to construct the bottom ring of in a related synchronous model that vields a sorted list from the system,which consists of all of the nodes sorted by their a degree-d weakly-connected graph of n nodes.We conjec- identifiers(randomly chosen in Chord,based on keys in skip ture that this lower bound is tight and could be attained by graphs).Constructing such a system thus depends on be- further improvements to our algorithms. ing able to sort nodes quickly;having done so,rebuilding the rest of the system takes little additional time.If build- Categories and Subject Descriptors ing a peer-to-peer system from scratch can be done quickly enough,the payoff is high:we can instantly deploy peer- C.2.4 [Computer-Communication Networks]:Distributed to-peer networks as needed as a tool in more complex dis- Systems-Distributed applications;F.2.2 Analysis of Al- tributed algorithms,and we can drop the cumbersome repair gorithms and Problem Complexity]:Nonnumerical Al- mechanisms found in many practical structured peer-to-peer gorithms and Problems systems in favor of a policy of periodic mass destruction and renewal. Supported in part by NSF grants CCR-0098078,CNS- 0305258.and CNS-0435201. In our model,we assume that any node can communi- TSupported by NSF grants CCR-0098078 and CNS-0305258. cate with any other node once it knows the other's address, and that initially,the nodes are organized into a weakly- +Supported by NSF grants CCR-0098078 and CNS-0305258. connected knowledge graph of bounded degree d,where a (directed)edge from u to v means that u knows u's ad- dress.Our algorithm proceeds by reorganizing this weakly- connected graph as a low-depth binary search tree where Permission to make digital or hard copies of all or part of this work for each node supplies both a leaf and at most one internal personal or classroom use is granted without fee provided that copies are node;the sorted list can then be read off of the leaves.Our not made or distributed for profit or commercial advantage and that copies algorithm has low contention:each node receives at most bear this notice and the full citation on the first page.To copy otherwise,to O(d)messages in a single round (in the synchronous version republish,to post on servers or to redistribute to lists,requires prior specific permission and/or a fee. of the algorithm)or has at most O(d)pending undelivered SPA4'05.July 18-20,2005,Las Vegas,Nevada,USA. messages at any time (in the asynchronous version).It also Copyright2005ACM1-58113-986-1/05/0007..$5.00 uses only short messages,of size proportional to the nodeFast Construction of Overlay Networks Dana Angluin Dept. Comp. Sci. Yale University New Haven, CT 06520 dana.angluin@yale.edu James Aspnes ∗ Dept. Comp. Sci. Yale University New Haven, CT 06520 aspnes@cs.yale.edu Jiang Chen Dept. Comp. Sci. Yale University New Haven, CT 06520 jiang.chen@yale.edu Yinghua Wu † Dept. Comp. Sci. Yale University New Haven, CT 06520 y.wu@yale.edu Yitong Yin ‡ Dept. Comp. Sci. Yale University New Haven, CT 06520 yitong.yin@yale.edu ABSTRACT An asynchronous algorithm is described for rapidly con￾structing an overlay network in a peer-to-peer system where all nodes can in principle communicate with each other di￾rectly through an underlying network, but each participat￾ing node initially has pointers to only a handful of other participants. The output of the mechanism is a linked list of all participants sorted by their identifiers, which can be used as a foundation for building various linear overlay net￾works such as Chord or skip graphs. Assuming the initial pointer graph is weakly-connected with maximum degree d and the length of a node identifier is W, the mechanism constructs a binary search tree of nodes of depth O(W) in expected O(W log n) time using expected O((d+W)n log n) messages of size O(W) each. Furthermore, the algorithm has low contention: at any time there are only O(d) unde￾livered messages for any given recipient. A lower bound of Ω(d + log n) is given for the running time of any procedure in a related synchronous model that yields a sorted list from a degree-d weakly-connected graph of n nodes. We conjec￾ture that this lower bound is tight and could be attained by further improvements to our algorithms. Categories and Subject Descriptors C.2.4 [Computer-Communication Networks]: Distributed Systems—Distributed applications; F.2.2 [Analysis of Al￾gorithms and Problem Complexity]: Nonnumerical Al￾gorithms and Problems ∗ Supported in part by NSF grants CCR-0098078, CNS- 0305258, and CNS-0435201. † Supported by NSF grants CCR-0098078 and CNS-0305258. ‡ Supported by NSF grants CCR-0098078 and CNS-0305258. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SPAA’05, July 18–20, 2005, Las Vegas, Nevada, USA. Copyright 2005 ACM 1-58113-986-1/05/0007 ...$5.00. General Terms Algorithms Theory Keywords Overlay networks, asynchronous, merging, Patricia trees 1. INTRODUCTION Consider the problem of rapidly building a peer-to-peer system with a ring or line structure such as Chord [19] or skip graphs [3]. The default assumption in both systems ap￾pears to be that nodes will be inserted sequentially, giving a construction time of O(n log2 n) for Chord and O(n log n) for skip graphs. But how quickly can we build such a sys￾tem if we do so in parallel, assuming that initially each node only knows about a few other nodes in the system? At min￾imum, we need to be able to construct the bottom ring of the system, which consists of all of the nodes sorted by their identifiers (randomly chosen in Chord, based on keys in skip graphs). Constructing such a system thus depends on be￾ing able to sort nodes quickly; having done so, rebuilding the rest of the system takes little additional time. If build￾ing a peer-to-peer system from scratch can be done quickly enough, the payoff is high: we can instantly deploy peer￾to-peer networks as needed as a tool in more complex dis￾tributed algorithms, and we can drop the cumbersome repair mechanisms found in many practical structured peer-to-peer systems in favor of a policy of periodic mass destruction and renewal. In our model, we assume that any node can communi￾cate with any other node once it knows the other’s address, and that initially, the nodes are organized into a weakly￾connected knowledge graph of bounded degree d, where a (directed) edge from u to v means that u knows v’s ad￾dress. Our algorithm proceeds by reorganizing this weakly￾connected graph as a low-depth binary search tree where each node supplies both a leaf and at most one internal node; the sorted list can then be read off of the leaves. Our algorithm has low contention: each node receives at most O(d) messages in a single round (in the synchronous version of the algorithm) or has at most O(d) pending undelivered messages at any time (in the asynchronous version). It also uses only short messages, of size proportional to the node