Full text  Click to download. 
Citation  In Proc. of 17th ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA) 2005

Authors  Krishnaram Kenthapadi
G. S. Manku 
We study randomized algorithms for placing a sequence of
n nodes on a circle with unit perimeter. Nodes divide the circle
into disjoint arcs. We desire that a newlyarrived node (which
is oblivious of its index in the sequence) choose its position
on the circle by learning the positions of as few ex isting
nodes as possible. At the same time, we desire that that the
variation in arclengths be small. To this end, we propose a new
algorithm that works as follows: The kth node chooses r random
points on the circle, inspects the sizes of v arcs in the
vicinity of each random point, and places itself at the
midpoint of the largest arc encountered. We show that for any
combination of r and v satisfying rv >= c log k, where c is a
small constant, the ratio of the largest to the small est
arclength is at most eight w.h.p., for an arbitrarily long
sequence of n nodes. This strategy of node placement under lies
a novel decentralized loadbalancing algorithm that we propose
for Distributed Hash Tables (DHTs) in peertopeer
environments.
Underlying the analysis of our algorithm is Structured Coupon
Collection over n/b disjoint cliques with b nodes per clique,
for any n, b >= 1. Nodes are initially uncovered. At each step,
we choose d nodes independently and uniformly at random. If all
the nodes in the corresponding cliques are covered, we do
nothing. Otherwise, from among the chosen cliques with at least
one uncovered nodes, we select one at random and cover and
uncovered nodes within that clique. We show that as long as bd
>= c log n, O(n) steps are sufficient to cover all ndoes w.h.p.
and each of the first \omega(n) steps succeeds in covering a
nodes w.h.p. These results are then utilized to analysis a
stochastic process for grownig binary trees that are highly
balanced  leaves of th etree belong to at most four different
levels with high probability.