The result that tie-breaking strategies which favor bins which are a
priori less likely to receive future load out-perform (at least in
practice, if not asymptotically) purely random strategies is one which
is generally rather intuitive.  Much less intuitive, however, is the
result that it is useful to introduce artificial asymmetries, even in
cases where it would be feasible to choose bins independently and
uniformly at random.  In a 1999 paper entitled ``How Asymmetry Helps
Load Balancing'' \cite{voecking99:_how_asymm_helps_load_balan},
V\"{o}cking presents a variation on the general power of two choices
scheme which intentionally produces asymmetries, and shows how it
out-performs purely symmetric schemes using independent uniform
distributions.

V\"{o}cking's algorithm, called \proc{Always-Go-Left}, performs
significantly better than the standard power-of-two-choices algorithm,
producing a maximum load of at most $\frac{\ln\ln n}{d\ln\phi_d} +
O(1)$ with high probability, where $\phi_d < 2$ is an extension of the
golden ratio.  Notably, in this scheme, the maximum load decreases
linearly with the number of choices, whereas in the classic scheme it
only decreased as as the logarithm of the number of choices.  This
algorithm works by partitioning the bins into $d$ groups of size
$\Theta \frac{n}{d}$, then choosing one bin from each group for each
incoming ball, with the choice of a bin within a group being uniform
and independent for each ball.  If two bins are equally loaded, an
asymmetric tie-breaking strategy is used, in which the bin with the
lowest index is chosen preferentially.  Using a witness tree argument,
V\"{o}cking proves that the loading of an already heavy bin is
significantly less likely in this scheme than in the classic one, to
an extent which produces a better asymptotic runtime.

This result is surprising mainly because, on the surface, it is quite
counter-intuitive.  Since all bins are equally likely to be chosen,
the natural assumption would be that an unbiased tie-breaking strategy
would perform best, as the end goal is to create as close to an even
distribution of balls in bins as possible.  However, when the bin
choices are being made dependently, this intuition does not stand.
Since the smaller indexed bin is chosen, there will be a tendency for
the groups of bins with smaller numbers to fill faster.  This is a
good thing, however, when one bin from each group is chosen for each
ball, as it means that the more full bins are more concentrated in
certain groups, so the probability of highly filled bins being chosen
from every group is low.

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