Overview of Processes

On this page, we summarise various balanced allocation processes. To discover more about a process and run visualisations with more bins, click on the ναμε of a process. You can also run additional steps of the processes by clicking the visualiser.

One-Choice

The $\OneChoice$ process is the simplest randomised allocation process. Each ball is allocated to a bin sampled uniformly at random. It is well-known that this proces has w.h.p. $\Gap(m) = \Theta(\sqrt{\frac{m}{n} \cdot \log n})$ for any $m \geq n$.

Your browser does not support the HTML5 canvas tag.

Two-Choice

The $\TwoChoice$ process is an improvement over $\OneChoice$, where for each ball two bins are sampled uniformly at random. The ball is then allocated to the least loaded of the two bins. $\TwoChoice$ achieves w.h.p. $\Gap(m) = \Theta(\log \log n)$ for any $m \geq n$ ("power of two choices").

Your browser does not support the HTML5 canvas tag.

(1+β)-Process

The $\OnePlusBeta$-process is a mix of $\OneChoice$ and $\TwoChoice$. This means that each ball is allocated with probability $\beta \in (0, 1]$ using $\TwoChoice$ and with probability $1-\beta$ using $\OneChoice$.

Your browser does not support the HTML5 canvas tag.

Mean-Thinning

The $\MeanThinning$ process samples a bin uniformly at random and if its load is at most the average, then it allocates to it. Otherwise, it allocates to a bin sampled uniformly at random. This process achieves w.h.p. $\Gap(m) = \Theta(\log n)$, while being more sample efficient than $\TwoChoice$

Your browser does not support the HTML5 canvas tag.

Memory

The $\Memory$ process can store a bin in a cache. For each ball, it samples one bin uniformly at random and allocates to the least loaded of the cache and the bin. Then, it updates the cache to store the least loaded of the two.

Your browser does not support the HTML5 canvas tag.

Twinning

The $\Twinning$ process samples one bin uniformly at random and allocates two balls if it is an underloaded bin or one ball if it overloaded. Despite being very similar to the $\OneChoice$ process, it achieves w.h.p. $\Gap(m) = \Oh(\log n)$ gap and it is more sample efficient.

Your browser does not support the HTML5 canvas tag.

Packing

The $\Packing$ process samples one bin uniformly at random and allocates as many balls as needed to make the bin overloaded; or just one ball if it already is.

Your browser does not support the HTML5 canvas tag.