On this page, you will find a few visualisations for the processes mentioned in "Balanced Allocations with the Choice of Noise" by D. Los and T. Sauerwald, presented at the 41st ACM Symposium on Principles of Distributed Computing (PODC'22) [arxiv, doi, slides]. The general visualiser may also be of interest.
The $\OneChoice$ process is the simplest randomised allocation process. Each ball is allocated to a bin sampled uniformly at random.
The $\TwoChoice$ process is an improvement over $\OneChoice$, where for each ball two bins are sampled uniformly. The ball is then allocated in the least loaded of the two bins.
The $\GBounded$ setting is an adversarial noisy setting. For instance, for $\TwoChoice$ we sample two bins $i_1$ and $i_2$, and if there load difference is at most $g$, then we allocate to the heavier bin; otherwise we allocate to the lighter bin.
The $\GMyopic$ setting is similar to the $\GBounded$ setting. However, whenever we sample two bins $i_1$ and $i_2$ whose load difference is at most $g$, then we allocate to a random of the two bins; otherwise we allocate to the lighter bin.
The simplest outdated information setting is the $\Batched$ setting, where balls are allocated in batches of size $b$.
For small values of $b$, the $\TwoChoice$ process is optimal, but for larger values $b$, other processes, like the $\OnePlusBeta$-process, are superior.
$\TwoChoice$
$(1+\beta)$-Process
In the $\TauDelay$ setting, two bins are chosen randomly and the adversary may report any load values from the last $\tau$ steps. On the right, the adversary always tries to force placing to the heavier bin, by picking the smallest possible load for the heavier bin and the largest possible for the lightest bin.
In the $\SigmaNoisyLoad$ setting, two bins are chosen randomly and then their loads are perturbed by some normal noise $\mathcal{N}(0, \sigma^2)$. This means that some of the allocations are to the heavier of the two bin samples.