Consider the following stochastic process executed on a graph G = (V, E) whose nodes are initially uncovered. In each step, pick a node at random and if it is uncovered, cover it. Otherwise, if it has an uncovered neighbor, cover a random uncovered neighbor. Else, do nothing. This can be viewed as a structured coupon collector process. We show that for a large family of graphs, O(n) steps suffice to cover all nodes of the graph with high probability, where n is the number of vertices. Among these graphs are d-regular graphs with d = Ω(log n log log n), random d-regular graphs with d = Ω(log n) and the k-dimensional hypercube where n = 2 k . This process arises naturally in answering a question on load balancing in peer-to-peer networks. We consider a distributed hash table in which keys are partitioned across a set of processors, and we assume that the number of processors * Supported by NSF Research Infrastructure Award EIA-0080119 and by NSF Faculty Early Career Development Award CCR-0133664 † Supported in part by NSF grants CCR-9820951 and CCR-0121555 and DARPA cooperative agreement F30602-00-2-0601. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. grows dynamically, starting with a single processor. If at some stage there are n processors, the number of queries required to find a key is log 2 n + O(1), the number of pointers maintained by each processor is log 2 n + O(1), and moreover the worst ratio between the loads of processors is O(1), with high probability. To the best of our knowledge, this is the first analysis of a distributed hash table that achieves asymptotically optimal load balance, while still requiring only O(log n) pointers per processor and O(log n) queries for locating a key; previous methods required Ω(log 2 n) pointers per processor and Ω(log n) queries for locating a key.
Adler et al REF present a DHT which provably ensures that, as nodes join the system, the ratio of loads of any two nodes is O(1) with high probability.
A stochastic process on the hypercube with applications to peer-to-peer networks
STOC '03
Computer Science