BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T102037Z
UID:Seminar-dept-1012@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20220920T130000
DTEND:20220920T140000
SUMMARY:School Seminar Series
DESCRIPTION:Prof. Thomas Sauerwald: Balanced Allocations: The Power of Choice versus Noise\n\nIn 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.\n\n\n\nIn 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.\n\n\n\nThis is based on joint works with Dimitrios Los.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1012
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR