Balanced Allocations: The Power of Choice versus Noise

Add to your list(s) Download to your calendar using vCal

• Dr Thomas Sauerwald - Department of Computer Science and Technology
• Wednesday 01 June 2022, 15:05-15:55
• Lecture Theatre 1, Computer Laboratory, William Gates Building.

If you have a question about this talk, please contact Ben Karniely.

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 work with Dimitrios Los.

Link to join virtually: https://cl-cam-ac-uk.zoom.us/j/97767639783?pwd=T09GcVJxZUNEUFEvRnZnbWwxeEwzQT09

A recording of this talk is available to University of Cambridge members at the following link: https://www.cl.cam.ac.uk/seminars/wednesday/video/

This talk is part of the Wednesday Seminars - Department of Computer Science and Technology series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Chris Davis' list
• Department of Computer Science and Technology talks and seminars
• Graduate-Seminars
• Guy Emerson's list
• Interested Talks
• Lecture Theatre 1, Computer Laboratory, William Gates Building
• School of Technology
• Trust & Technology Initiative - interesting events
• Wednesday Seminars - Department of Computer Science and Technology
• bld31
• computer science
• se393's list

Note that ex-directory lists are not shown.