Structured Coupon Collection over Cliques for P2P Load Balance: ID Mangement and Load Balance in Distributed Hash Tables

Abstract

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.