Document Open Access Logo

Balanced Allocations with Incomplete Information: The Power of Two Queries

Authors Dimitrios Los, Thomas Sauerwald

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.103.pdf
  • Filesize: 1.1 MB
  • 23 pages

Document Identifiers

Author Details

Dimitrios Los
  • Department of Computer Science & Technology, University of Cambridge, UK
Thomas Sauerwald
  • Department of Computer Science & Technology, University of Cambridge, UK

Funding

  • Sauerwald, Thomas: The author was supported by the ERC grant "Dynamic March". Part of this work was done while visiting Hasso-Plattner Institute, Potsdam, Germany.

Cite As Get BibTex

Dimitrios Los and Thomas Sauerwald. Balanced Allocations with Incomplete Information: The Power of Two Queries. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 103:1-103:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.103

Abstract

We consider the allocation of m balls into n bins with incomplete information. In the classical Two-Choice process a ball first queries the load of two randomly chosen bins and is then placed in the least loaded bin. In our setting, each ball also samples two random bins but can only estimate a bin’s load by sending binary queries of the form "Is the load at least the median?" or "Is the load at least 100?". 
For the lightly loaded case m = 𝒪(n), Feldheim and Gurel-Gurevich (2021) showed that with one query it is possible to achieve a maximum load of 𝒪(√{log n/log log n}), and they also pose the question whether a maximum load of m/n+𝒪(√{log n/log log n}) is possible for any m = Ω(n). In this work, we resolve this open problem by proving a lower bound of m/n+Ω(√{log n}) for a fixed m = Θ(n √{log n}), and a lower bound of m/n+Ω(log n/log log n) for some m depending on the used strategy. 
We complement this negative result by proving a positive result for multiple queries. In particular, we show that with only two binary queries per chosen bin, there is an oblivious strategy which ensures a maximum load of m/n+𝒪(√{log n}) for any m ≥ 1. Further, for any number of k = 𝒪(log log n) binary queries, the upper bound on the maximum load improves to m/n + 𝒪(k(log n)^{1/k}) for any m ≥ 1. 
This result for k queries has several interesting consequences: (i) it implies new bounds for the (1+β)-process introduced by Peres, Talwar and Wieder (2015), (ii) it leads to new bounds for the graphical balanced allocation process on dense expander graphs, and (iii) it recovers and generalizes the bound of m/n+𝒪(log log n) on the maximum load achieved by the Two-Choice process, including the heavily loaded case m = Ω(n) which was derived in previous works by Berenbrink et al. (2006) as well as Talwar and Wieder (2014). 
One novel aspect of our proofs is the use of multiple super-exponential potential functions, which might be of use in future work.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probability and statistics
  • Mathematics of computing → Discrete mathematics
  • Theory of computation → Randomness, geometry and discrete structures
  • Theory of computation → Design and analysis of algorithms
Keywords
  • power-of-two-choices
  • balanced allocations
  • potential functions
  • thinning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dan Alistarh, Trevor Brown, Justin Kopinsky, Jerry Zheng Li, and Giorgi Nadiradze. Distributionally linearizable data structures. In Proceedings of 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA'18), pages 133-142, 2018. URL: https://doi.org/10.1145/3210377.3210411.
  2. Dan Alistarh, Rati Gelashvili, and Joel Rybicki. Fast graphical population protocols, 2021. URL: http://arxiv.org/abs/2102.08808.
  3. Dan Alistarh, Giorgi Nadiradze, and Amirmojtaba Sabour. Dynamic averaging load balancing on cycles. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP'20), volume 168, pages 7:1-7:16, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.7.
  4. Noga Alon, Ori Gurel-Gurevich, and Eyal Lubetzky. Choice-memory tradeoff in allocations. Ann. Appl. Probab., 20(4):1470-1511, 2010. URL: https://doi.org/10.1214/09-AAP656.
  5. Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM J. Comput., 29(1):180-200, 1999. URL: https://doi.org/10.1137/S0097539795288490.
  6. Nikhil Bansal and Ohad Feldheim. Well-balanced allocation on general graphs, 2021. URL: http://arxiv.org/abs/2106.06051.
  7. Itai Benjamini and Yury Makarychev. Balanced allocation: memory performance tradeoffs. Ann. Appl. Probab., 22(4):1642-1649, 2012. URL: https://doi.org/10.1214/11-AAP804.
  8. Petra Berenbrink, Artur Czumaj, Matthias Englert, Tom Friedetzky, and Lars Nagel. Multiple-choice balanced allocation in (almost) parallel. In Proceedings of 16th International Workshop on Approximation, Randomization, and Combinatorial Optimization (RANDOM'12), pages 411-422, 2012. URL: https://doi.org/10.1007/978-3-642-32512-0_35.
  9. Petra Berenbrink, Artur Czumaj, Angelika Steger, and Berthold Vöcking. Balanced allocations: the heavily loaded case. SIAM J. Comput., 35(6):1350-1385, 2006. URL: https://doi.org/10.1137/S009753970444435X.
  10. Petra Berenbrink, Kamyar Khodamoradi, Thomas Sauerwald, and Alexandre Stauffer. Balls-into-bins with nearly optimal load distribution. In Proceedings of 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'13), pages 326-335, 2013. URL: https://doi.org/10.1145/2486159.2486191.
  11. Fan Chung and Linyuan Lu. Concentration inequalities and martingale inequalities: a survey. Internet Math., 3(1):79-127, 2006. URL: https://doi.org/10.1080/15427951.2006.10129115.
  12. Fan R. K. Chung. Spectral graph theory, volume 92 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997. URL: https://doi.org/10.1090/cbms/092.
  13. Artur Czumaj and Volker Stemann. Randomized allocation processes. Random Structures Algorithms, 18(4):297-331, 2001. URL: https://doi.org/10.1002/rsa.1011.
  14. D. L. Eager, E. D. Lazowska, and J. Zahorjan. Adaptive load sharing in homogeneous distributed systems. IEEE Transactions on Software Engineering, SE-12(5):662-675, 1986. URL: https://doi.org/10.1109/TSE.1986.6312961.
  15. Guy Even and Moti Medina. Parallel randomized load balancing: a lower bound for a more general model. Theoret. Comput. Sci., 412(22):2398-2408, 2011. URL: https://doi.org/10.1016/j.tcs.2011.01.033.
  16. Ohad N. Feldheim and Ori Gurel-Gurevich. The power of thinning in balanced allocation. Electron. Commun. Probab., 26:Paper No. 34, 8, 2021. URL: https://doi.org/10.1214/21-ecp400.
  17. Ohad N. Feldheim, Ori Gurel-Gurevich, and Jiange Li. Long-term balanced allocation via thinning, 2021. URL: http://arxiv.org/abs/2110.05009.
  18. Ohad Noy Feldheim and Jiange Li. Load balancing under d-thinning. Electronic Communications in Probability, 25:Paper No. 1, 13, 2020. URL: https://doi.org/10.1214/19-ecp282.
  19. Kazuo Iwama and Akinori Kawachi. Approximated two choices in randomized load balancing. In Proceedings of 15th International Symposium on Algorithms and Computation (ISAAC'04), volume 3341, pages 545-557. Springer-Verlag, 2004. URL: https://doi.org/10.1007/978-3-540-30551-4_48.
  20. Y. Kanizo, D. Raz, and A. Zlotnik. Efficient use of geographically spread cloud resources. In Proceedings of 13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, pages 450-457, 2013. URL: https://doi.org/10.1109/CCGrid.2013.18.
  21. R. M. Karp, M. Luby, and F. Meyer auf der Heide. Efficient PRAM simulation on a distributed memory machine. Algorithmica, 16(4-5):517-542, 1996. URL: https://doi.org/10.1007/BF01940878.
  22. Krishnaram Kenthapadi and Rina Panigrahy. Balanced allocation on graphs. In Proceedings of 17th ACM-SIAM Symposium on Discrete Algorithms (SODA'06), pages 434-443, 2006. URL: https://doi.org/10.1145/1109557.1109606.
  23. Christoph Lenzen, Merav Parter, and Eylon Yogev. Parallel balanced allocations: The heavily loaded case. In Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA'19), pages 313-322. ACM, 2019. URL: https://doi.org/10.1145/3323165.3323203.
  24. Christoph Lenzen and Roger Wattenhofer. Tight bounds for parallel randomized load balancing [extended abstract]. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC'11), pages 11-20, 2011. URL: https://doi.org/10.1145/1993636.1993639.
  25. Dimitrios Los, Thomas Sauerwald, and John Sylvester. Balanced allocations: Caching and packing, twinning and thinning, 2021. URL: http://arxiv.org/abs/2110.10759.
  26. M. Mitzenmacher. On the analysis of randomized load balancing schemes. Theory Comput. Syst., 32(3):361-386, 1999. URL: https://doi.org/10.1007/s002240000122.
  27. Michael Mitzenmacher, Andréa W. Richa, and Ramesh Sitaraman. The power of two random choices: a survey of techniques and results. In Handbook of randomized computing, Vol. I, II, volume 9 of Comb. Optim., pages 255-312. Kluwer Acad. Publ., Dordrecht, 2001. URL: https://doi.org/10.1007/978-1-4615-0013-1_9.
  28. Yuval Peres, Kunal Talwar, and Udi Wieder. Graphical balanced allocations and the (1+β)-choice process. Random Structures Algorithms, 47(4):760-775, 2015. URL: https://doi.org/10.1002/rsa.20558.
  29. A. Steger and N. C. Wormald. Generating random regular graphs quickly. Combinatorics, Probability and Computing, 8(4):377-396, 1999. URL: https://doi.org/10.1017/S0963548399003867.
  30. Volker Stemann. Parallel balanced allocations. In Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'96), pages 261-269, 1996. URL: https://doi.org/10.1145/237502.237565.
  31. Kunal Talwar and Udi Wieder. Balanced allocations: the weighted case. In Proceedings of 39th ACM Symposium on Theory of Computing (STOC'07), pages 256-265, 2007. URL: https://doi.org/10.1145/1250790.1250829.
  32. Kunal Talwar and Udi Wieder. Balanced allocations: a simple proof for the heavily loaded case. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP'14), volume 8572, pages 979-990, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_81.
  33. Konstantin Tikhomirov and Pierre Youssef. The spectral gap of dense random regular graphs. Ann. Probab., 47(1):362-419, 2019. URL: https://doi.org/10.1214/18-AOP1263.
  34. Udi Wieder. Hashing, load balancing and multiple choice. Found. Trends Theor. Comput. Sci., 12(3-4):275-379, 2017. URL: https://doi.org/10.1561/0400000070.
  35. S. Zhou. A trace-driven simulation study of dynamic load balancing. IEEE Transactions on Software Engineering, 14(9):1327-1341, 1988. URL: https://doi.org/10.1109/32.6176.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact