Towards fast decentralized construction of locality-aware overlay networks
Aleksandrs Slivkins · 2007
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 ip-addresses. 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.