skip to main content
research-article

An Improved Drift Theorem for Balanced Allocations

Published: 11 October 2024 Publication History

Abstract

In the balanced allocations framework, there are \(m\) jobs (balls) to be allocated to \(n\) servers (bins). The goal is to minimize the gap, the difference between the maximum and the average load.
In 2015, Peres, Talwar and Wieder used the hyperbolic cosine potential function to analyze the challenging case where \(m\gg n\), for a large family of processes, including the \((1+\beta)\)-process and graphical balanced allocations. The key ingredient was to prove that the potential drops in every step, i.e., a drift inequality.
In this work, we improve the drift inequality so that (i) it is asymptotically tight (leading to tighter gap bounds), (ii) it assumes weaker preconditions (thereby resolving an open problem regarding weighted graphical allocations), (iii) it applies not only to processes allocating to more than one bin in a single step but also (iv) to processes allocating a varying number of balls depending on the sampled bin. Our applications include the aforementioned large family of processes, and also several new processes and settings, including outdated information and memory. We hope that our techniques can be used to analyze further interesting settings and processes.

References

[1]
Micah Adler, Soumen Chakrabarti, Michael Mitzenmacher, and Lars Rasmussen. 1998. Parallel randomized load balancing. Random Structures & Algorithms 13, 2 (1998), 159–188. DOI:
[2]
Dan Alistarh, James Aspnes, and Rati Gelashvili. 2018. Space-optimal majority in population protocols. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’18). SIAM, 2221–2239. DOI:
[3]
Dan Alistarh, Trevor Brown, Justin Kopinsky, Jerry Zheng Li, and Giorgi Nadiradze. 2018. Distributionally linearizable data structures. In Proceedings of the 30th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’18). ACM, New York, NY, 133–142. DOI:
[4]
Dan Alistarh, Rati Gelashvili, and Joel Rybicki. Fast graphical population protocols. 2021. In Proceedings of the 25th International Conference on Principles of Distributed Systems (OPODIS’21), Vol. 217. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 14:1–14:18. DOI:
[5]
Dan Alistarh, Justin Kopinsky, Jerry Li, and Giorgi Nadiradze. 2017. The power of choice in priority scheduling. In Proceedings of the 36th Annual ACM-SIGOPT Principles of Distributed Computing (PODC’17). ACM, New York, NY, 283–292. DOI:
[6]
Dan Alistarh, Giorgi Nadiradze, and Amirmojtaba Sabour. 2020. Dynamic averaging load balancing on cycles. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP’20), Vol. 168. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 7:1–7:16. DOI:
[7]
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. 1999. Balanced allocations. SIAM Journal on Computing 29, 1 (1999), 180–200. DOI:
[8]
Nikhil Bansal and Ohad N. Feldheim. 2022. The power of two choices in graphical allocation. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC’22). ACM, New York, NY, 52–63. DOI:
[9]
Nikhil Bansal and William Kuszmaul. 2022. Balanced allocations: The Heavily loaded case with deletions. In Proceedings of the 63th Annual IEEE Symposium on Foundations of Computer Science (FOCS’22). IEEE, 801–812. DOI:
[10]
Petra Berenbrink, Artur Czumaj, Matthias Englert, Tom Friedetzky, and Lars Nagel. 2012. Multiple-choice balanced allocation in (almost) parallel. In Proceedings of the 16th International Workshop on Randomization and Computation (RANDOM’12). Springer-Verlag, 411–422. DOI:
[11]
Petra Berenbrink, Artur Czumaj, Angelika Steger, and Berthold Vöcking. 2006. Balanced allocations: the heavily loaded case. SIAM Journal on Computing 35, 6 (2006), 1350–1385. DOI:
[12]
Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars Nagel, and Chris Wastell. 2018. Self-stabilizing balls and bins in batches: The power of leaky bins. Algorithmica 80, 12 (2018), 3673–3703. DOI:
[13]
Petra Berenbrink, Kamyar Khodamoradi, Thomas Sauerwald, and Alexandre Stauffer. 2013. Balls-into-bins with nearly optimal load distribution. In Proceedings of the 25th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’13). ACM, New York, NY, 326–335. DOI:
[14]
Richard Cole, Alan M. Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Ramesh K. Sitaraman, and Eli Upfal. 1998. On balls and bins with deletions. In Proceedings of the 2nd International Workshop on Randomization and Computation (RANDOM’98), Lecture Notes in Computer Science, Vol. 1518. Springer, 145–158. DOI:
[15]
Artur Czumaj and Volker Stemann. Randomized allocation processes. 2001. Random Structures & Algorithms 18, 4 (2001), 297–331. DOI:
[16]
Devdatt P. Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge. DOI:
[17]
Guy Even and Moti Medina. 2011. Parallel randomized load balancing: a lower bound for a more general model. Theoretical Computer Science 412, 22 (2011), 2398–2408. DOI:
[18]
Ohad N. Feldheim and Ori Gurel-Gurevich. 2021. The power of thinning in balanced allocation. Electronic Communications in Probability 26 (2021), Paper No. 34, 8. DOI:
[19]
Ohad N. Feldheim, Ori Gurel-Gurevich, and Jiange Li. 2021. Long-term balanced allocation via thinning. The Annals of Applied Probability 34, 1A (2021), 795–850. DOI:
[20]
Ohad N. Feldheim and Jiange Li. 2020. Load balancing under \(d\)-thinning. Electronic Communications in Probability 25 (2020), Paper No. 1, 13. DOI:
[21]
P. Brighten Godfrey. 2008. Balls and bins with structure: balanced allocations on hypergraphs. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’08). 511–517.
[22]
Catherine S. Greenhill, Bernard Mans, and Ali Pourmiri. 2020. Balanced allocation on dynamic hypergraphs. In Proceedings of the 24th International Workshop on Randomization and Computation (RANDOM’20), Vol. 176. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 11:1–11:22. DOI:
[23]
Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Sahil Singla. 2020. Online carpooling using expander decompositions. In Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’20), Vol. 182. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 23:1–23:14. DOI:
[24]
Richard M. Karp, Michael Luby, and Friedhelm Meyer auf der Heide. 1996. Efficient PRAM simulation on a distributed memory machine. Algorithmica 16, 4–5 (1996), 517–542. DOI:
[25]
Krishnaram Kenthapadi and Rina Panigrahy. 2006. Balanced allocation on graphs. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’06). SIAM, 434–443. DOI:
[26]
Christoph Lenzen, Merav Parter, and Eylon Yogev. 2019. Parallel balanced allocations: The heavily loaded case. In Proceedings of the 31th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’19). ACM, New York, NY, 313–322. DOI:
[27]
Christoph Lenzen and Roger Wattenhofer. 2011. Tight bounds for parallel randomized load balancing: Extended abstract. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC’11). ACM, New York, NY, 11–20. DOI:
[28]
Dimitrios Los and Thomas Sauerwald. 2022. Balanced allocations in batches: Simplified and generalized. In Proceedings of the 34th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’22). ACM, New York, NY, 389–399. DOI:
[29]
Dimitrios Los and Thomas Sauerwald. 2022. Balanced allocations with incomplete information: The power of two queries. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS’22), Vol. 215. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 103:1–103:23. DOI:
[30]
Dimitrios Los and Thomas Sauerwald. 2023. Balanced allocations in batches: The tower of two choices. In Proceedings of the 35th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’23). ACM, New York, NY, 51–61. DOI:
[31]
Dimitrios Los, Thomas Sauerwald, and John Sylvester. 2022. Balanced allocations: Caching and packing, twinning and thinning. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’22). SIAM, 1847–1874. DOI:
[32]
Dimitrios Los, Thomas Sauerwald, and John Sylvester. 2023. Balanced allocations with heterogeneous bins: The power of memory. In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’23). SIAM, 4448–4477. DOI:
[33]
Michael Mitzenmacher. 1999. On the analysis of randomized load balancing schemes. Theory of Computing Systems 32, 3 (1999), 361–386. DOI:
[34]
Michael Mitzenmacher, Balaji Prabhakar, and Devavrat Shah. 2002. Load balancing with memory. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’02). IEEE, 799–808. DOI:
[35]
Michael Mitzenmacher, Andréa W. Richa, and Ramesh Sitaraman. 2001. The power of two random choices: A survey of techniques and results. In Handbook of Randomized Computing, Vol. 1. Sanguthevar Rajasekaran, Panos M. Pardalos, J. H. Reif, and José Rolim (Eds.), Kluwer Academic Publishers, Netherlands, 255–312. DOI:
[36]
Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (2nd ed.). Cambridge University Press, Cambridge.
[37]
Yuval Peres, Kunal Talwar, and Udi Wieder. 2015. Graphical balanced allocations and the \((1+\beta)\)-choice process. Random Structures & Algorithms 47, 4 (2015), 760–775. DOI:
[38]
Volker Stemann. Parallel balanced allocations. 1996. In Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’96). ACM, New York, NY, 261–269. DOI:
[39]
Kunal Talwar and Udi Wieder. 2007. Balanced allocations: The weighted case. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC’07). ACM, New York, NY, 256–265. DOI:
[40]
Udi Wieder. Hashing, load balancing and multiple choice. 2017. Foundations and Trends in Theoretical Computer Science 12, 3–4 (2017), 275–379. DOI:

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms
ACM Transactions on Algorithms  Volume 20, Issue 4
October 2024
416 pages
EISSN:1549-6333
DOI:10.1145/3613685
  • Editor:
  • Edith Cohen
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 October 2024
Online AM: 01 July 2024
Accepted: 08 June 2024
Revised: 12 October 2023
Received: 12 October 2023
Published in TALG Volume 20, Issue 4

Check for updates

Author Tags

  1. Balls-into-bins
  2. balanced allocations
  3. potential functions
  4. drift theorem
  5. heavily loaded
  6. gap bounds
  7. maximum load
  8. memory
  9. two-choices
  10. weighted balls

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 132
    Total Downloads
  • Downloads (Last 12 months)132
  • Downloads (Last 6 weeks)11
Reflects downloads up to 12 Feb 2025

Other Metrics

Citations

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Full Text

View this article in Full Text.

Full Text

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media