Prof. Dr. Ohad Noy Feldheim, Hebrew University of Jerusalem
Consider kn balls (tasks) allocated at random into n bins (servers). On average, each bin is expected to receive k balls, but some fluctuations are inevitable and the number of balls in the most loaded bin will be of order log n/log log n.
In a seminal 1994 paper, Azar, Broader, Karlin and Upfal showed that if rather than placing each ball at random, we are given the choice between two possible uniformly chosen random allocations, then by putting the ball in the one which received less balls so far, the maximum load is reduced exponentially to be of order log log n. This discovery has since led to countless extensions, variations and real life applications.
In the talk I will focus on the results and variants which contribute to the understanding of the origin of this phenomenon and its robustness. We will ask:
- How independent should the two suggested bins be?
- What is the impact of adding noise to the allocation?
- What kind of information is needed to effectively use the choice?
- When is a more involved strategy for optimal use of our choice called for?
- How do any of the answers change when rather than throwing just O(n) balls, we throw them ad inifinitum.
In the course of (partially) answering these questions we will adopt a "statistical mechanics" point of view on the problem and show that, in fact, there are two forces in action here, one which is very fragile, and one which is rather robust.
If you wish to attend one (or more) of the talks please send to request for the zoom link to anapde_mathematik.tu-darmstadt.de (please replace _ by @ ). Please include in your mail your full name, status (teacher, professor, student,...) and institution.
Wenn Sie als Zuhörer*in an den Kolloquien teilnehmen möchten, schicken Sie bitte eine Anfrage per Mail an anapde_mathematik.tu-darmstadt.de (ersetzen Sie dabei bitte _ durch @ ). Ihre Mail sollte Ihren vollständigen Namen, Ihren Status (Lehrer*in, Professor*in, Student*in, Doktorand*in , ...) und Ihre Institution enthalten.
12. Januar 2022, 17:15-19:00
FB Mathematik, AG Numerik und wissenschaftliches Rechnen
Prof. Dr. Jan Giesselmann