Randomized ID Selection for Peer to Peer Networks

Full textClick to download.
CitationIn Proc. of ACM Symposium on Principles of Distributed Computing, 2004, pp 197-205
AuthorG. S. Manku


We present a low-cost, decentralized algorithm for ID management in distributed hash tables (DHTs) managed by a dynamic set of hosts. Each host is assigned an ID in the unit interval [0,1]. At any time, the set of IDs splits the interval into disjoint partitions. Hosts do not possess global knowledge of other IDs in the system. The challenge then is to design an efficient decentralized algorithm that maintains roughly equi-sized partitions, in the face of arrivals, departures and changes in the average number of hosts. Our ID management algorithm is the first to enjoy all of the following properties: (a) both arrivals and departures of hosts are handled, (b) departure of a host causes at most one existing host to change its ID, (c) the ratio of the largest to the smallest partition is at most 4, with high probability, and (d) the expected cost per arrival/departure is \theta(R+log(n)) messages, where n denotes the current number of participants, and R denotes the cost of routing one message in the DHT. In fact, our algorithm is independent of the topology of the overlay network used for routing. Variations of our algorithm diminish the ratio between the largest and the smallest partition to (1 + \epsilon) for any \spsilon > 0, albeit at the cost of re-assigning the IDs of O(1/\epsilon) existing hosts per arrival/departure. Ours is the first algorithm that allows such fine-tuning. Finally, our ID management algorithm enables (a) estimation of the total number of hosts in the system by making only local measurements, and (b) emulation of a variety of deterministic and randomized families of routing topologies, in a straightforward fashion. Among these families are several networks that require O(log(n)/log(k)) routing hope in an n-node network with k links per node.

Back to publications
Back to previous page