Balanced Allocations: The Power of Choice versus Noise

20^th September 2022, 13:00 Ashton Lecture Theatre
Prof. Thomas Sauerwald
Department of Computer Science and Technology, University of Cambridge

Abstract

In the balanced allocation problem we wish to allocate m balls (jobs) into n bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintain a small gap between the maximum load and average load. For the one-choice protocol, where each ball is allocated to a random bin, the gap diverges for large m. However, for the two-choice protocol, where each ball samples two bins and is placed in the least loaded of the two, it was shown that gap is only O(log log n) for all m. This dramatic improvement is widely known as ``power of two choices’’, and similar effects have been observed in hashing and routing.

In this talk, we will first give some intuition why two-choice maintains such a good balance in practice and theory. Then we will present our recent results in settings where the load information is subject to some noise. For example, the queried load information of bins might be (i) outdated, (ii) subject to some adversarial or random perturbation or (iii) only retrievable by binary queries. We prove that, roughly speaking, if the noise is not too strong, then performance is not affected and the O(log log n) gap bound of two-choice still holds. We also exhibit settings with strong noise and show that having more choices can lead to a worse performance.

This is based on joint works with Dimitrios Los.

Additional Materials

• https://arxiv.org/abs/2206.07503