×
Feldheim, Ohad Noy; Gurel-Gurevich, Ori; Li, Jiange

Long-term balanced allocation via thinning. (English) Zbl 1534.60014

Ann. Appl. Probab. 34, No. 1A, 795-850 (2024).
Summary: In the two-thinning balls-and-bins model, an overseer is provided with uniform random allocation of \(m\) balls into \(n\) bins in an on-line fashion. The overseer may reject the allocation of each ball, in which case it is placed into a new bin, drawn independently, uniformly at random. The purpose of the overseer is to reduce the maximum load, that is, the difference between the maximum number of balls in a single bin and the average number of balls among all bins.
We provide tight estimates for three quantities: the lowest achievable maximum load at a given time \(m\), the lowest achievable maximum load uniformly over the entire time interval \([m] : = \{1, 2, \dots, m\}\) and the lowest achievable typical maximum load over the interval \([m]\), that is, a load which upper-bounds \(1 - o(1)\) portion of the times in \([m]\).
In particular, for \(m\) polynomial in \(n\) and sufficiently large, we provide an explicit strategy, which achieves a typical maximum load of \((\log n)^{1 / 2 + o (1)}\), asymptotically the same as that can be achieved at a single time \(m\). In contrast, we show that no strategy can achieve better than \(\Theta(\frac{\log n}{\log \log n})\) maximum load for all times up to time \(m\).

Cited in 1 Document

MSC:

60C05 Combinatorial probability
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
68W20 Randomized algorithms

Keywords:

balls-and-bins; load balancing; two-choice; two-thinning
Cite Review PDF
Full Text: DOI arXiv Link

References:

[1] ADLER, M., CHAKRABARTI, S., MITZENMACHER, M. and RASMUSSEN, L. (1998). Parallel randomized load balancing. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC’95) 238-247. · Zbl 0968.68569
[2] ALON, N., GUREL-GUREVICH, O. and LUBETZKY, E. (2010). Choice-memory tradeoff in allocations. Ann. Appl. Probab. 20 1470-1511. Digital Object Identifier: 10.1214/09-AAP656 Google Scholar: Lookup Link MathSciNet: MR2676945 · Zbl 1205.60023 · doi:10.1214/09-AAP656
[3] AZAR, Y., BRODER, A. Z., KARLIN, A. R. and UPFAL, E. (1999). Balanced allocations. SIAM J. Comput. 29 180-200. Digital Object Identifier: 10.1137/S0097539795288490 Google Scholar: Lookup Link MathSciNet: MR1710347 · Zbl 0937.68053 · doi:10.1137/S0097539795288490
[4] BENJAMINI, I. and MAKARYCHEV, Y. (2012). Balanced allocation: Memory performance tradeoffs. Ann. Appl. Probab. 22 1642-1649. Digital Object Identifier: 10.1214/11-AAP804 Google Scholar: Lookup Link MathSciNet: MR2985172 · Zbl 1246.68163 · doi:10.1214/11-AAP804
[5] BERENBRINK, P., BRINKMANN, A., FRIEDETZKY, T. and NAGEL, L. (2014). Balls into non-uniform bins. J. Parallel Distrib. Comput. 74 2065-2076. · Zbl 1327.68042
[6] BERENBRINK, P., CZUMAJ, A., STEGER, A. and VÖCKING, B. (2006). Balanced allocations: The heavily loaded case. SIAM J. Comput. 35 1350-1385. Digital Object Identifier: 10.1137/S009753970444435X Google Scholar: Lookup Link MathSciNet: MR2217150 · Zbl 1114.68082 · doi:10.1137/S009753970444435X
[7] Daley, D. J. and Vere-Jones, D. (2003). An Introduction to the Theory of Point Processes. Vol. I: Elementary Theory and Methods, 2nd ed. Probability and Its Applications (New York). Springer, New York. MathSciNet: MR1950431 · Zbl 1026.60061
[8] Daley, D. J. and Vere-Jones, D. (2008). An Introduction to the Theory of Point Processes. Vol. II: General Theory and Structure, 2nd ed. Probability and Its Applications (New York). Springer, New York. Digital Object Identifier: 10.1007/978-0-387-49835-5 Google Scholar: Lookup Link MathSciNet: MR2371524 · Zbl 1159.60003 · doi:10.1007/978-0-387-49835-5
[9] DEMBO, A. and ZEITOUNI, O. (2010). Large Deviations Techniques and Applications, 2nd ed. Stochastic Modelling and Applied Probability 38. Springer, Berlin. Digital Object Identifier: 10.1007/978-3-642-03311-7 Google Scholar: Lookup Link MathSciNet: MR2571413 · Zbl 1177.60035 · doi:10.1007/978-3-642-03311-7
[10] DWIVEDI, R., FELDHEIM, O. N., GUREL-GUREVICH, O. and RAMDAS, A. (2019). The power of online thinning in reducing discrepancy. Probab. Theory Related Fields 174 103-131. Digital Object Identifier: 10.1007/s00440-018-0860-y Google Scholar: Lookup Link MathSciNet: MR3947321 · Zbl 1421.68246 · doi:10.1007/s00440-018-0860-y
[11] EAGER, D. L., LAZOWSKA, E. D. and ZAHORJAN, J. (1986). Adaptive load sharing in homogeneous distributed systems. IEEE Trans. Softw. Eng. SE-12 662-675.
[12] FELDHEIM, O. N. and GUREL-GUREVICH, O. (2021). The power of thinning in balanced allocation. Electron. Commun. Probab. 26 Paper No. 34, 8. Digital Object Identifier: 10.1214/21-ecp400 Google Scholar: Lookup Link MathSciNet: MR4275960 · Zbl 1494.60012 · doi:10.1214/21-ecp400
[13] FELDHEIM, O. N. and LI, J. (2020). Load balancing under \(d\)-thinning. Electron. Commun. Probab. 25 Paper No. 1, 13. Digital Object Identifier: 10.1214/19-ecp282 Google Scholar: Lookup Link MathSciNet: MR4053904 · Zbl 1428.60102 · doi:10.1214/19-ecp282
[14] GODFREY, P. B. (2008). Balls and bins with structure: Balanced allocations on hypergraphs. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms 511-517. ACM, New York. MathSciNet: MR2487619 · Zbl 1192.90225
[15] KARP, R. M., LUBY, M. and MEYER AUF DER HEIDE, F. (1992). Efficient PRAM simulation on a distributed memory machine. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC’92) 318-325.
[16] KENTHAPADI, K. and PANIGRAHY, R. (2006). Balanced allocation on graphs. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms 434-443. ACM, New York. Digital Object Identifier: 10.1145/1109557.1109606 Google Scholar: Lookup Link MathSciNet: MR2368840 · Zbl 1192.68462 · doi:10.1145/1109557.1109606
[17] LOS, D. and SAUERWALD, T. (2022). Balanced allocations with incomplete information: The power of two queries. In 13th Innovations in Theoretical Computer Science Conference. LIPIcs. Leibniz Int. Proc. Inform. 215 Art. No. 103, 23. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern. MathSciNet: MR4459474 · Zbl 07829335
[18] LOS, D., SAUERWALD, T. and SYLVESTER, J. (2022). Balanced allocations: Caching and packing, twinning and thinning. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 1847-1874. SIAM, Philadelphia, PA. Digital Object Identifier: 10.1137/1.9781611977073.74 Google Scholar: Lookup Link MathSciNet: MR4415111 · Zbl 07883655 · doi:10.1137/1.9781611977073.74
[19] MITZENMACHER, M., PRABHAKAR, B. and SHAH, D. (2002). Load balancing with memory. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS’02) 799-808.
[20] MITZENMACHER, M., RICHA, A. W. and SITARAMAN, R. (2001). The power of two random choices: A survey of techniques and results. In Handbook of Randomized Computing, Vol. I, II. Comb. Optim. 9 255-312. Kluwer Academic, Dordrecht. Digital Object Identifier: 10.1007/978-1-4615-0013-1_9 Google Scholar: Lookup Link MathSciNet: MR1966907 · Zbl 1056.68166 · doi:10.1007/978-1-4615-0013-1_9
[21] MITZENMACHER, M. and UPFAL, E. (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge Univ. Press, Cambridge. Digital Object Identifier: 10.1017/CBO9780511813603 Google Scholar: Lookup Link MathSciNet: MR2144605 · Zbl 1092.60001 · doi:10.1017/CBO9780511813603
[22] PERES, Y., TALWAR, K. and WIEDER, U. (2015). Graphical balanced allocations and the \((1 + \mathit{\beta})\)-choice process. Random Structures Algorithms 47 760-775. Digital Object Identifier: 10.1002/rsa.20558 Google Scholar: Lookup Link MathSciNet: MR3418914 · Zbl 1347.68365 · doi:10.1002/rsa.20558
[23] Raab, M. and Steger, A. (1998). “Balls into bins”—A simple and tight analysis. In Randomization and Approximation Techniques in Computer Science (Barcelona, 1998). Lecture Notes in Computer Science 1518 159-170. Springer, Berlin. Digital Object Identifier: 10.1007/3-540-49543-6_13 Google Scholar: Lookup Link MathSciNet: MR1729169 · Zbl 0928.60001 · doi:10.1007/3-540-49543-6_13
[24] SANDERS, P., EGNER, S. and KORST, J. (2003). Fast concurrent access to parallel disks. Algorithmica 35 21-55. Digital Object Identifier: 10.1007/s00453-002-0987-0 Google Scholar: Lookup Link MathSciNet: MR1938242 · Zbl 1026.68013 · doi:10.1007/s00453-002-0987-0
[25] STEMANN, V. (1996). Parallel balanced allocations. In Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’96) 261-269.
[26] TALWAR, K. and WIEDER, U. (2007). Balanced allocations: The weighted case. In STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing 256-265. ACM, New York. Digital Object Identifier: 10.1145/1250790.1250829 Google Scholar: Lookup Link MathSciNet: MR2402449 · Zbl 1232.68170 · doi:10.1145/1250790.1250829
[27] TALWAR, K. and WIEDER, U. (2014). Balanced allocations: A simple proof for the heavily loaded case. In Automata, Languages, and Programming. Part I. Lecture Notes in Computer Science 8572 979-990. Springer, Heidelberg. Digital Object Identifier: 10.1007/978-3-662-43948-7_81 Google Scholar: Lookup Link MathSciNet: MR3238686 · Zbl 1410.68073 · doi:10.1007/978-3-662-43948-7_81
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.