The general idea behind the power of two choices is a rather simple
one.  As originally introduced in a 1994 paper entitled ``Balanced
Allocations,'' by Azar, Broder, Karlin, and
Upfal~\cite{azar94:_balan_alloc}, and analyzed at great length in
Mitzenmacher's 1996 PhD thesis entitled ``The Power of Two Choices in
Randomized Load Balancing''~\cite{mitzenmacher96:_power_of_two_choic},
the power of two choices is a paradigm for load balancing which is
capable of an exponential improvement in asymptotic performance over
the obvious load balancing strategy.  All it entails, however, is that
instead of assigning load uniformly at randomly, one should pick two
independently and uniformly random possibilities as load arrives, and
always choose the less loaded of the two.

While the general principle is simple, the improvement in asymptotic
performance is remarkable.  It is well known that the obvious load
balancing strategy of assigning load uniformly at random produces a
maximum load of $\frac{(1+o(1))\log n}{\log\log n}$ with high
probability.  However, when load is assigned sequentially, and the
power of two choices is used, the maximum load drops to
$\frac{\log\log n}{\log 2} + O(1)$ with high probability, which is
effectively exponentially better than the obvious strategy.  The power
of two choices paradigm has the drawback that load needs to be
assigned sequentially, rather than in parallel.  In any system where
this is possible, though, it offers a marked improvement in load
balancing, while only increasing the computation needed each time load
is assigned by at most a constant factor. Generalizing to $d$ random
choices instead of 2, we obtain the following result:

\begin{theorem}
  \label{thm:potc}
  If $n$ balls are assigned to $n$ bins using the load-balancing
  technique where each ball chooses $d$ bins, and is placed in the
  least-loaded of these $d$ bins, the maximum load is $\frac{\log\log
    n}{\log d} + O(1)$ with high probability.
\end{theorem}
\begin{proof}
  The idea is simple, but a rigorous proof involves many technical
  details related to handling conditioning, which we shall omit; for
  the details, see \cite{azar00:_balan_alloc} or
  \cite{mitzenmacher96:_power_of_two_choic}.

  We consider the number of bins containing at least $i$ balls. If
  $\beta_i$ is a bound on the number of bins with at least $i$ balls,
  then the probability that any ball becomes the $i+1$st in its bin is
  bounded by $\left( \frac{\beta_i}{n} \right)^d$ since this requires
  that each of the $d$ bins chosen is one of the $\beta_i$ with at
  least $i$ balls. Using Bernoulli processes to bound the number of
  such balls, we obtain a relation
  \begin{equation}
    \label{eq:potc-bi}
    \beta_{i+1} = \bigO{\left( \frac{\beta_i}{n} \right)^d}
  \end{equation}
  Using \eqref{eq:potc-bi} and induction (which requires considerable
  care with conditioning), we can see that the sequence
  $\nicefrac{\beta_i}{n}$ decreases exponentially with $i$, and so
  after $\log_d \log n + \bigO{1}$ steps, it decreases below 1. Thus,
  with high probability, there is no bin with load greater than
  $\log_d \log n + \bigO{1} = \frac{\log\log n}{\log d} + O(1)$
\end{proof}

\begin{remark}  
  Notice that using two random choices instead of one gives a very
  dramatic improvement from $\bigO{\frac{\log n}{\log \log n}}$ to
  $\bigO{\log \log n}$, but adding additional choices only gives a
  smaller improvement by changing the base of the outer logarithm.
\end{remark}

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