One notable limitation of the seminal works on the power of two choices is      
the reliance on the supposition that bins are chosen uniformly at random.       
In practice, however, not all bins are created equal.  When dealing with a      
distributed system, for example, some servers might be a priori more            
likely to be chosen to handle an incoming item.  In particular, this is a       
situation which arises in many distributed hash tables, in which each           
server is assigned to a random point on a circle, and handles all items         
which fall between itself and the nearest server to its left.  In this          
particular situation, each server is responsible for incoming items             
falling into an average of $\frac{1}{n}$ of the circle, but, because their      
loci are random, there is potentially a large variance in the fractions of      
incoming items assigned to each server. We discuss this application
further in Section~\ref{sec:applications:p2p}.

In a 2004 paper entitled ``Geometric Generalizations of the Power of
Two Choices'' \cite{byers04:_geomet_gener_of_power_of_two_choic},
Byers, Considine, and Mitzenmacher address this issue.  In this paper,
an inductive argument which directly parallels that made in the
original paper by Azar et al.~\cite{azar00:_balan_alloc} is presented,
proving that the maximum load of any bin when using the power of $d$
choices and circular locus assignment is $\frac{\log\log n}{\log d} +
O(1)$ with high probability, which differs from the classical result
on a uniform distribution only in the constant factor.  Furthermore,
they generalize to a more abstract case in which the sizes of the $n$
bins are determined through an unspecified random process which has
the properties that the maximum bin size is at most $\delta_1\frac{\ln
  n}{n}$ with high probability and the number of bins of size at least
$\frac{c}{n}$ is bounded by
$\delta_2ne^{-\frac{c}{\delta_3}}$ with probability $1 - o(\frac{1}{n^2})$      
for all $c$ in the range $2 \leq c \leq \delta_4\ln n$.  These properties       
are held by a number of distributions, and, most notably, are held by           
schemes involving placing servers on both circles and two-dimensional tori      
and assigning to them the regions to which they are the closest
server.

Furthermore, in this paper, experimental results are shown which
demonstrate the practical usefulness of the power of two choices in a
distributed hashing system using the circular locus paradigm.  In the
results shown, placement based on a single choice results in maximum
loads which seem to match the $O(\log n)$ prediction nicely, topping
out at a maximum reported load of 32 when running 1000 trials of
placing $2^{24}$ balls into $2^{24}$ bins.  By contrast, using two
choices reduced the maximum load to at most 6 for over 4000 trials,
ranging from $n = 2^{12}$ to $n = 2^{24}$.  As predicted, increasing
the number of choices to 3 or 4 had only a small impact on the
observed maximum load.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "paper"
%%% End: