Overview of Settings

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 (see "tower of two choices").

The $\GBounded$ setting is an adversarial noisy setting for processes sampling two bins in each step. The adversary can decide the outcome of comparisons for bins where load differs by at most $g$. For instance, for the $\TwoChoice$ process, we sample two bins $i_1$ and $i_2$, and if their 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.

In the Repeated Balls-into-Bins (RBB) setting, there is always a fixed number of balls in the system. In each round, one ball is removed from each non-empty bin and it is randomly re-allocated to one of the bins.

In the heterogeneous sampling setting, the bins are sampled according to a biased distribution. Wieder (2007) showed that for small biases, $\TwoChoice$ still maintains the $\Oh(\log \log n)$ gap (e.g. left), while for others the gap diverges. In constrast, we show that the $\Memory$ process can maintain the $\Oh(\log \log n)$ gap even under arbitrary constant biases.

In the $\TauDelay$ setting, two bins are sampled uniformly at random and the adversary may report any load values from the last $\tau$ steps. On the right, we see an instance of this setting for the $\TwoChoice$, where 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.