Towards Fast Decentralized Construction of Locality-Aware Overlay Networks

We consider a large overlay network where any two nodes can communicate directly via the underlying
Internet as long as the sender knows the recipient’s ip-address. Due to the scalability requirement,
the overlay network must be sparse: a given node can store at most a polylogarithmic number of ipaddresses.
A notion of distance (locality) in the network is given by node-to-node round-trip times. We
assume that initially the overlay links are random, and hence have no explicit locality-aware properties.
We provide fast distributed constructions for various locality-aware (low-stretch) distributed data
structures, such as: distance labeling schemes, name-independent routing schemes, and multicast trees.
In previous work, such data structures have only been constructed via centralized algorithms. Our constructions
complete in poly-logarithmic time (and thus induce at most a poly-logarithmic load on every
given node), and achieve quality guarantees similar to those of the corresponding centralized algorithms.
Our algorithms use a common locality-aware, small-world-like overlay framework, constructed via
concurrent random walks. Our guarantees are for growth-constrained metrics, a well-studied family of
metrics which have been proposed as a reasonable abstraction of round-trip times in the Internet.