Kenthapadi, Krishnaram and Manku, Gurmeet Singh (2004) Structured Coupon Collection over Cliques for P2P Load Balance: ID Mangement and Load Balance in Distributed Hash Tables. Technical Report. Stanford.
We study Structured Coupon Collection over n/b disjoint cliques with b nodes per clique. Nodes are initially uncovered. At each step, we choose d nodes independently and uniformly at random. If all nodes in the corresponding cliques are covered, we do nothing. Otherwise, from among the chosen cliques with at least one uncovered node, we select one at random and cover an uncovered node within that clique. We show that as long as bd > c log n, O(n) steps are sufficient to cover all nodes w.h.p. and each of the first \Omega(n) steps succeed in covering some node w.h.p. These results are then utilized to analyze a stochastic process for growing binary trees that are highly balanced -- the leaves of the tree belong to at most four different levels w.h.p. The stochastic process constitutes the core idea underlying a practical P2P load balancing scheme that beats earlier proposals for the same, in terms of message complexity.
|Item Type:||Techreport (Technical Report)|
|Additional Information:||This paper has been submitted to SODA 2005.|
|Uncontrolled Keywords:||Load Balance, ID Management, Distributed Hash Tables, Structured Coupon Collection, Cliques|
|Subjects:||Computer Science > Distributed Systems|
|Related URLs:||Project Homepage||http://infolab.stanford.edu/peers/|
|Deposited By:||Import Account|
|Deposited On:||31 Jul 2004 17:00|
|Last Modified:||23 Dec 2008 09:17|
Repository Staff Only: item control page