Many computer applications require some form of load balancing.  Such
applications range from assigning tasks to processor queues to
assigning data to nodes to peer to peer networks.  While these
numerous problems vary greatly in many respects, there is a simple
technique, first studied in the early 1990s, which can introduce a
surprisingly large improvement into many of them.  This technique is
known as \emph{the power of two choices}.

The basic intuition of this concept can be best explained using the
classic \emph{balls and bins} problem, in which there are $n$ balls
which have to be placed in $n$ bins.  When a ball has to be assigned
to a bin, two bins are chosen independently uniformly at random, and
the ball is placed in the less full of the two.  In the more general
case, the ball is placed in the least full of $d$ randomly chosen
bins.  Although it might seem counterintuitive that such a simplistic
method for bin assignment should work well, the maximum load in any
bin after $n$ balls are placed is bounded by $\log \log n + \bigO{1}$
with high probability. This is a substantial improvement over the
$\bigTheta{\frac{\log n}{\log \log n}}$ result that can be obtained by
simply choosing one bin uniformly at random.  Moreover, due to the
minimal amount of computation that goes into making a decision, this
result can be achieved using only $\bigO{d}$ computation time per item
to be assigned.

This method is easy to implement and produces very satisfying results,
so it has been the source for many research improvements since its
introduction.  There are, for example, many variations on this simple
theme, where the basic idea is tweaked in some simple way to achieve
improvements in the maximum load bound.  In one approach, asymmetric
tie-breaking is added by always choosing the leftmost bin.  In
another, the best options from the previous decision round are
remembered, and these are among the options for the next time an item
is to be assigned to a bin. Finally, the technique can be extended to
more general geometries where each bin is not chosen uniformly, but
rather proportional to the size of some area it is responsible for.

We will also examine some applications that have benefited form this
technique. It can be used to analyze queue lengths in a server
load-balancing problem known as the \emph{supermarket model}, to
distribute load more effectively in peer-to-peer networks based on
consistent hashing, and to improve hashing in high-performance
routers.

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