####
Geometric Generalizations of the Power of Two Choices

A well-known paradigm for load balancing in parallel and distributed
systems is the ``power of two choices,'' whereby an item is stored
at the less loaded of two (or more) random alternative servers. We
investigate the power of two choices in natural settings where items
and servers reside in a geometric space and each item is associated
with the server that is its nearest neighbor. This is the setting
for the Chord distributed hash table, where the geometric space is
determined by clockwise distance on a one-dimensional ring. For
example, our analysis shows that when n items are placed in n
bins, the maximum load at any server is log log n/ log d + O(1)
with high probability, only an additive constant more than when
servers are chosen uniformly at random. Our proofs are quite
general, showing that the power of two choices works under a variety
of distributions, with most geometric constructions having at most
an additive O(1) penalty. We also show that these techniques
still work under highly unbalanced distributions, and give sharp
bounds on the necessary number of choices. Finally, we provide
simulation results demonstrating the load balance that results as
the system size scales into the millions.