On this page, we give a brief introduction to balanced allocations processes and the power of two choices. Then, we proceed to give a summary of the our main results and insights.
Power of Two Choices
In the balanced allocations framework, we are given $m$ tasks (balls) to allocate into $n$ servers (bins). The goal is to minimise the maximum load of a bin or equivalently the gap, which is the difference of maximum to average load. In a centralised setting, this can be solved optimally by allocating the balls to the bins in a round-robin manner. However, in a decentralised setting, we need to explore processes that assume less coordination between the bins.
The $\OneChoice$ process is the simplest such allocation process. Each ball is allocated to a bin sampled uniformly at random. It is well-known that w.h.p. $\Gap(m) = \Theta(\sqrt{\frac{m}{n} \cdot \log n})$ for any $m \geq n \log n$. On the figure on the right, the horizontal line represents the average load. By clicking on the figure, you can run the process for a few more steps.
The $\TwoChoice$ process is an improvement over $\OneChoice$, where for each ball two bins are sampled uniformly. The ball is then allocated to the least loaded of the two bins. Berenbrink, Czumaj, Steger and Vöcking (2006) showed that w.h.p. $\Gap(m) = \Theta(\log \log n)$ for any $m \geq n$, and so the gap does not diverge as $m \to \infty$.
This difference in the performance of the $\OneChoice$ and the $\TwoChoice$ processes is known as the "power of two choices". By clicking on the play button below you can observe that the gap of $\OneChoice$ diverges while that of $\TwoChoice$ remains small.
$\OneChoice$
$\TwoChoice$
.
.
The significance of the power of two choices paradigm was recently recognised by the 2020 ACM Theory and Practice award:
[..] it is not surprising that the power of two choices that requires only a local decision rather than global coordination has led to a wide range of practical applications. These include i-Google’s web index, Akamai’s overlay routing network, and highly reliable distributed data storage systems used by Microsoft and Dropbox, which are all based on variants of the power of two choices paradigm.
However, the sequential allocations setting makes simplifying assumptions compared to real-world load balancing and so several drawbacks of $\TwoChoice$ have been identified:
The power of two choices suffers from two remaining performance problems: first, server queue length is a poor indicator of wait time, and second, due to messaging delays, multiple schedulers sampling in parallel may experience race conditions. -- SPARROW (2013)
More importantly, the $\TwoChoice$ algorithm requires communication between dispatchers and processors at the time of job assignment. The communication time is on the critical path, hence contributes to the increase in response time. -- Join-Idle-Queue (2011)
The main focus of the dissertation was to analyse the performance of $\TwoChoice$ and its variants in settings making more realistic assumptions for outdated information, noise and incomplete information.
Variants of the Two-Choice Process
Several variants of the $\TwoChoice$ process have been studied that trade off sample-efficiency, the amount of coordination between the bins, and gap guarantees.
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$. Peres, Talwar and Wieder (2010) showed that for any $\beta$ the gap does not diverge for any $\beta \in (0, 1]$. In this work, we obtain tight bounds for small and large $\beta$ (for $\beta = 1$ recovering the bound for $\TwoChoice$).
Another sample-efficient family of processes are the $\TwoThinning$ processes, where for each ball, up to two bins are sampled and the decision on whether to accept or reject a bin is made in an online manner. We study $\RelativeThreshold$ processes that use thresholds at a fixed offset from the average. Compared to $\TwoChoice$, these processes reduce the amount of coordination between the bins, as shown in the figure below:
A prototypical such process is $\MeanThinning$, which allocates to the first bin sample if its load is at most the average; otherwise it allocates to a bin sampled uniformly at random. We show that this achieves $\Gap(m) = \Oh(\log n)$ and by a coupling this also implies tight bound for other $\RelativeThreshold$ processes.
Outdated Information
One idealistic assumption made by the sequential balanced allocations framework is that the reported load of a sampled bin is an exact estimate of its load. Mitzenmacher (2000) introduced the $\Batched$, where balls are allocated in batches of size $b$ in parallel. Berenbrink, Czumaj, Englert, Friedetzky and Nagel (2012) analysed the case $b = n$ for $\TwoChoice$ and proved that w.h.p. $\Gap(m) = \Oh(\log n)$. In this work, we improve this bound to $\Oh(\log n/\log \log n)$ and show that for $b \leq n \log n$, the gap of the $\TwoChoice$ matches the gap of $\OneChoice$ for $b$ balls and so it is asymptotically optimal.
On the contrary, for larger batch sizes $b \geq n \log n$ we show that $\TwoChoice$ has $\Gap(m) = \Theta(b/n)$ and slightly surprisingly we demonstrate that there exist instances of $\OnePlusBeta$-process that achieve the optimal $\Theta(\sqrt{b/n \cdot \log n})$ gap. Most of these results hold for a large family of processes and in the presense of weights. The experiments below demonstrate this almost quadratic improvement. On a high level, this is because $\TwoChoice$ allocates aggressively to light bins, while the $\OnePlusBeta$-process is more gentle (see also this figure).
$\TwoChoice$
$\OnePlusBeta$-process (for $\beta = 0.6$)
.
.
Further, for the $\TwoChoice$ process, we study a setting that relaxes the assumption of the $\Batched$ setting that the loads of the bins are all synchronised at the same round every $b$ steps. In the $\TauDelay$ setting, two bins are chosen randomly and an adversary may choose to report any load values from the last $\tau$ steps. On the right, the adversary always tries to force allocating to the heavier bin, by picking the smallest possible load for the heavier bin and the largest possible for the lightest bin.
Adversarial & Random Noise Setting
For the $\TwoChoice$ process, we analyse the aforementioned outdated information settings, by reducing them to the adversarial setting, where an adversary can decide the outcome of a comparison for bins whose loads are at most $g \in \N_+$. This setting also allows us to analyse $\TwoChoice$ with random noise. For any $g$, we prove tight bounds for the following two processes:
The $\GBounded$ process was introduced by Alistarh, Brown, Kopinsky, Li and Nadiradze (2018) to analyse the multi-counter data structure. For each ball, we sample two bins uniformly at random, 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$ process which is less aggressive than the $\GBounded$ process, in that whenever we sample two bins whose load difference is at most $g$, then we allocate randomly to one of the two; otherwise we allocate to the lighter bin.
Power of Filling
We also explore the "power of filling" underloaded bins as an alternative way of maintaining balanced allocations. For two processes $\Twinning$ and $\Packing$, we show that they achieve $\Gap(m) = \Oh(\log n)$ and a sample efficiency that is better than that of $\OneChoice$. Further, these bounds also apply to allocations on $d$-regular graphs, including the cycle where it has been conjectured that $\TwoChoice$ has $\Gap(m) = \Omega(\sqrt{n})$.
The $\Twinning$ process samples one bin uniformly at random and allocates two balls if the bin is underloaded or one ball if it is overloaded.
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.
Power of Memory
Mitzenmacher, Prabhakar, and Shah (2002) introduced the $\Memory$ process which 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.
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, while for larger biases the gap diverges as $m \to \infty$. In our work, we show that for any constant bias in the sampling distribution, the $\Memory$ process maintains the $\Oh(\log \log n)$ gap.
The experiments below demonstrate this "power of memory": (left) $\TwoChoice$ for small bias has a small gap, (middle) $\TwoChoice$ for large bias has a gap that diverges and (right) $\Memory$ for the same bias has a small gap.
$\TwoChoice~(\alpha = 0.1)$
$\TwoChoice~(\alpha = 0.5)$
$\Memory~(\alpha = 0.5)$
Power of Two Queries
For any $\TwoThinning$ process, we prove a lower bound of $\Omega(\log n/\log \log n)$, resolving an open problem of Feldheim and Gurel-Gurevich (2021). We also study the $\KThreshold(f_1, \ldots, f_k)$ processes, an extension of $\TwoThinning$ processes where the allocator sends to each bin, $k$ queries of the form "Is your load at most $f_i$?". We devise a process with $k$ queries which achieves $\Gap(m) = \Oh(k \cdot (\log n)^{1/k})$. For $k = 2$, this establishes almost a quadratic improvement, which we call "power of two queries".
Other settings
In the Graphical setting, the bins are vertices of a graph and for each ball, one edge is sampled uniformly at random. The ball is then allocated to the least loaded of the two bins incident to the edge. We extend the $\Oh(\frac{\log n}{\phi})$ gap for graphs with conductance $\phi$ to the graphical setting with weights (and batches), resolving an open problem by Peres, Talwar and Wieder (2015). Further, we generalise the $o(\log n)$ bounds of Kenthapadi and Panigrahy (2006) for dense expanders to any $m \geq n$.
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.