Balanced Allocations: The Heavily Loaded Case with Deletions

Download PDF

In the 2-choice allocation problem, m balls are placed into n bins, and each ball must choose between two random bins i, j \in [n] that it has been assigned to. It has been known for more than two decades, that if each ball follows the Greedy strategy (i.e., always pick the less-full bin), then the maximum load will be m/n + O(\log \log n) with high probability in n (and m / n + O(\log m) with high probability in m). It has remained open whether the same bounds hold in the dynamic version of the same game, where balls are inserted/deleted with up to m balls present at a time.
We show that these bounds do not hold in the dynamic setting: already on 4 bins, there exists a sequence of insertions/deletions that cause {Greedy} to incur a maximum load of m/4 + \Omega(\sqrt{m}) with probability \Omega(1) -- this is the same bound as if each ball is simply assigned to a random bin!
This raises the question of whether any 2-choice allocation strategy can offer a strong bound in the dynamic setting. Our second result answers this question in the affirmative: we present a new strategy, called ModulatedGreedy, that guarantees a maximum load of m / n + O(\log m), at any given moment, with high probability in m. Generalizing ModulatedGreedy, we obtain dynamic guarantees for the (1 + \beta)-choice setting, and for the setting of balls-and-bins on a graph.
Finally, we consider a setting in which balls can be reinserted after they are deleted, and where the pair i, j that a given ball uses is consistent across insertions. This seemingly small modification renders tight load balancing impossible: on 4 bins, any strategy that is oblivious to the specific identities of balls must allow for a maximum load of m/4 + poly(m) at some point in the first poly(m) insertions/deletions, with high probability in m.