Balanced Allocations: The Power of Choice versus Noise

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 more than 20 years ago that the 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 present new results in settings where the load information is restricted or noisy. 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 also exhibit settings with strong noise and demonstrate that having more choices can lead to a worse performance.

This is based on joint works with Dimitrios Los and John Sylvester. More information and some illustrations of the results are also available under:

$\url{dimitrioslos.com/research/phd-thesis/index.html}$

computer science theorycombinatorics

Audience: researchers in the topic

University of Birmingham theoretical computer science seminar

Series comments: Meeting ID: 818 7333 5084 ~ Password: 217