The power-of-two-choices technique was a breakthrough in the
world of load balancing algorithms.  There are numerous applications
that have benefited greatly from the insight of the approach.  Among
these, of course, are the application discussed here, such as
supermarket load balancing, hash tables, and peer-to-peer
network load distribution.  These are, however, just a subset of the total
group of algorithms and applications that benefited.

In addition to its being a very useful technique on its own, the
power-of-two-choices technique has also spawned many variations on the
original theme.  The use of asymmetry or a stored state have also
introduced further improvements in the load balancing properties, and
the technique has been generalized to certain geometric problems where
the random selection is not uniform.
                                                                                
Much of the beauty of these techniques is their simplicity.  While the
proofs of their bounds might sometimes be complicated, the techniques
themselves are very straightforward and easy to implement.  The all
run in constant time per item to be assigned, so there is very little
overhead, and yet they provide a dramatic improvement in terms of
bounds on their maximum load.

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