# 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.

## Abstract

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.

- SPAA 2005 proceedings version:
**PDF**.

## BibTeX

Download@inproceedings(AngluinACWY2005,
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",
month=jul,
year=2005,
pages={145--154}
)

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page