License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.45
URN: urn:nbn:de:0030-drops-176975
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17697/
Los, Dimitrios ;
Sauerwald, Thomas
Tight Bounds for Repeated Balls-Into-Bins
Abstract
We study the repeated balls-into-bins process introduced by Becchetti, Clementi, Natale, Pasquale and Posta (2019). This process starts with m balls arbitrarily distributed across n bins. At each round t = 1,2,…, one ball is selected from each non-empty bin, and then placed it into a bin chosen independently and uniformly at random. We prove the following results:
- For any n ⩽ m ⩽ poly(n), we prove a lower bound of Ω(m/n ⋅ log n) on the maximum load. For the special case m = n, this matches the upper bound of ?(log n), as shown in [Luca Becchetti et al., 2019]. It also provides a positive answer to the conjecture in [Luca Becchetti et al., 2019] that for m = n the maximum load is ω(log n/ log log n) at least once in a polynomially large time interval. For m ∈ [ω(n), n log n], our new lower bound disproves the conjecture in [Luca Becchetti et al., 2019] that the maximum load remains ?(log n).
- For any n ⩽ m ⩽ poly(n), we prove an upper bound of ?(m/n ⋅ log n) on the maximum load for all steps of a polynomially large time interval. This matches our lower bound up to multiplicative constants.
- For any m ⩾ n, our analysis also implies an ?(m²/n) waiting time to reach a configuration with a ?(m/n ⋅ log m) maximum load, even for worst-case initial distributions.
- For m ⩾ n, we show that every ball visits every bin in ?(m log m) rounds. For m = n, this improves the previous upper bound of ?(n log² n) in [Luca Becchetti et al., 2019]. We also prove that the upper bound is tight up to multiplicative constants for any n ⩽ m ⩽ poly(n).
BibTeX - Entry
@InProceedings{los_et_al:LIPIcs.STACS.2023.45,
author = {Los, Dimitrios and Sauerwald, Thomas},
title = {{Tight Bounds for Repeated Balls-Into-Bins}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {45:1--45:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-266-2},
ISSN = {1868-8969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17697},
URN = {urn:nbn:de:0030-drops-176975},
doi = {10.4230/LIPIcs.STACS.2023.45},
annote = {Keywords: Repeated balls-into-bins, self-stabilizing systems, balanced allocations, potential functions, random walks}
}
