Fast construction of overlay networks

Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu, and Yitong Yin. Fast construction of overlay networks. Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, July 2005, pages 145–154.


An asynchronous algorithm is described for rapidly constructing an overlay network in a peer-to-peer system where all nodes can in principle communicate with each other directly through an underlying network, but each participating 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 networks 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) undelivered 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 conjecture that this lower bound is tight and could be attained by further improvements to our algorithms.


title="Fast construction of overlay networks",
author="Dana Angluin and James Aspnes and Jiang Chen and Yinghua Wu and Yitong Yin",
booktitle="Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures",

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page