Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins [Extended Abstract]

ABSTRACT

A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be distributed to n bins (servers). In a seminal work, [Azar et al.; JoC'99] proposed the sequential strategy Greedy[d] for n = m. When thrown, a ball queries the load of d random bins and is allocated to a least loaded of these. [Azar et al.; JoC'99] showed that d=2 yields an exponential improvement compared to d=1. [Berenbrink et al.; JoC'06] extended this to m ⇒ n, showing that the maximal load difference is independent of m for d=2 (in contrast to d=1).

We propose a new variant of an infinite balls into bins process. In each round an expected number of λ n new balls arrive and are distributed (in parallel) to the bins and each non-empty bin deletes one of its balls. This setting models a set of servers processing incoming requests, where clients can query a server's current load but receive no information about parallel requests. We study the Greedy[d] distribution scheme in this setting and show a strong self-stabilizing property: For any arrival rate λ=λ(n) < 1, the system load is time-invariant. Moreover, for any (even super-exponential) round t, the maximum system load is (w.h.p.) O(1 over 1-λ•logn over 1-λ) for d=1 and O(log n over 1-λ) for d=2. In particular, Greedy[2] has an exponentially smaller system load for high arrival rates.

References

1. M. Adler, P. Berenbrink, and K. Schröder. Analyzing an infinite parallel job allocation process. In Proceedings of the 6th Annual European Symposium on Algorithms, ESA '98, pages 417--428, London, UK, UK, 1998. Springer-Verlag. ISBN 3-540-64848-8. URL http://dl.acm.org/citation.cfm?id=647908.740138.
2. M. Adler, S. Chakrabarti, M. Mitzenmacher, and L. Rasmussen. Parallel randomized load balancing. Random Structures & Algorithms, 13 (2): 159--188, 1998. ISSN 1098-2418. 10.1002/(SICI)1098--2418 URL http://dx.doi.org/10.1002/(SICI)1098--2418(199809)13:2<159::AID-RSA3>3.0.CO;2-Q.
3. A. S. Alfa. Algorithmic analysis of the bmap/d/k system in discrete time. Adv. in Appl. Probab., 35 (4): 1131--1152, 12 2003. 10.1239/aap/1067436338. URL http://dx.doi.org/10.1239/aap/1067436338.
4. Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal. Balanced allocations. SIAM Journal on Computing, 29 (1): 180--200, 1999. 10.1137/S0097539795288490.
5. L. Becchetti, A. E. F. Clementi, E. Natale, F. Pasquale, and G. Posta. Self-stabilizing repeated balls-into-bins. In G. E. Blelloch and K. Agrawal, editors, Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, pages 332--339. ACM, 2015. ISBN 978-1-4503-3588-1. 10.1145/2755573.2755584. URL http://doi.acm.org/10.1145/2755573.2755584.
6. P. Berenbrink, A. Czumaj, T. Friedetzky, and N. D. Vvedenskaya. Infinite parallel job allocation (extended abstract). In phProceedings of the Twelfth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '00, pages 99--108, New York, NY, USA, 2000. ACM. ISBN 1-58113-185-2. 10.1145/341800.341813. URL http://doi.acm.org/10.1145/341800.341813.
7. P. Berenbrink, A. Czumaj, A. Steger, and B. Vöcking. Balanced allocations: The heavily loaded case. SIAM Journal on Computing, 35 (6): 1350--1385, 2006. 10.1137/S009753970444435X.
8. P. Berenbrink, A. Czumaj, M. Englert, T. Friedetzky, and L. Nagel. Multiple-choice balanced allocation in (almost) parallel. In A. Gupta, K. Jansen, J. Rolim, and R. Servedio, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 7408 of Lecture Notes in Computer Science, pages 411--422. Springer Berlin Heidelberg, 2012. ISBN 978-3-642-32511-3. 10.1007/978-3-642-32512-0_35. URL http://dx.doi.org/10.1007/978-3-642-32512-0_35.
9. P. Berenbrink, K. Khodamoradi, T. Sauerwald, and A. Stauffer. Balls-into-bins with nearly optimal load distribution. In Proceedings of the Twenty-fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13, pages 326--335, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-1572-2. 10.1145/2486159.2486191. URL http://doi.acm.org/10.1145/2486159.2486191.
10. P. Berenbrink, T. Friedetzky, P. Kling, F. Mallmann-Trenn, L. Nagel, and C. Wastell. Self-stabilizing balls & bins in batches. CoRR, abs/1603.02188, 2016. URL http://arxiv.org/abs/1603.02188.
11. A. Czumaj. Recovery time of dynamic allocation processes. In Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '98, pages 202--211, New York, NY, USA, 1998. ACM. ISBN 0-89791-989-0. 10.1145/277651.277686. URL http://doi.acm.org/10.1145/277651.277686.
12. A. Czumaj and V. Stemann. Randomized allocation processes. In Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on, pages 194--203, Oct 1997. 10.1109/SFCS.1997.646108.
13. G. Fayolle, V. Malyshev, and M. Menshikov. Topics in the Constructive Theory of Countable Markov Chains. Cambridge University Press, 1995. ISBN 9780521461979. URL https://books.google.ca/books?id=lTJltFEnnHcC.
14. G. H. Gonnet. Expected length of the longest probe sequence in hash code searching. J. ACM, 28 (2): 289--304, Apr. 1981. ISSN 0004-5411. 10.1145/322248.322254. URL http://doi.acm.org/10.1145/322248.322254.
15. B. Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, 14 (3): 502--525.
16. A. Kamal. Efficient solution of multiple server queues with application to the modeling of atm concentrators. In INFOCOM '96. Fifteenth Annual Joint Conference of the IEEE Computer Societies. Networking the Next Generation. Proceedings IEEE, volume 1, pages 248--254 vol.1, Mar 1996. 10.1109/INFCOM.1996.497900.
17. N. K. Kim, M. L. Chaudhry, B. K. Yoon, and K. Kim. A complete and simple solution to a discrete-time finite-capacity bmap/d/c queue. 2012.
18. D. A. Levin and Y. Perres. Markov Chains and Mixing Times. American Mathematical Society, December 2008. ISBN 978-0-8218-4739-8.
19. M. Mitzenmacher. The power of two choices in randomized load balancing. IEEE Trans. Parallel Distrib. Syst., 12 (10): 1094--1104, 2001. 10.1109/71.963420. URL http://doi.ieeecomputersociety.org/10.1109/71.963420.
20. Y. Peres, K. Talwar, and U. Wieder. The (1 β)-choice process and weighted balls-into-bins. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA '10, pages 1613--1619, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics. ISBN 978-0--898716--98--6.
21. M. Raab and A. Steger. "balls into bins" - A simple and tight analysis. In M. Luby, J. D. P. Rolim, and M. J. Serna, editors, Randomization and Approximation Techniques in Computer Science, Second International Workshop, RANDOM'98, Barcelona, Spain, October 8-10, 1998, Proceedings, volume 1518 of Lecture Notes in Computer Science, pages 159--170. Springer, 1998. ISBN 3-540-65142-X. 10.1007/3-540-49543-6_13. URL http://dx.doi.org/10.1007/3--540--49543--6_13.
22. K. Sohraby and J. Zhang. Spectral decomposition approach for transient analysis of multi-server discrete-time queues. In INFOCOM'92. Eleventh Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE, pages 395--404. IEEE, 1992.
23. V. Stemann. Parallel balanced allocations. In Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '96, pages 261--269, New York, NY, USA, 1996. ACM. ISBN 0-89791-809-6. 10.1145/237502.237565. URL http://doi.acm.org/10.1145/237502.237565.
24. K. Talwar and U. Wieder. Balanced allocations: A simple proof for the heavily loaded case. In J. Esparza, P. Fraigniaud, T. Husfeldt, and E. Koutsoupias, editors, Automata, Languages, and Programming, volume 8572 of Lecture Notes in Computer Science, pages 979--990. Springer Berlin Heidelberg, 2014. ISBN 978-3-662-43947-0. 10.1007/978-3-662-43948-7_81. URL http://dx.doi.org/10.1007/978--3--662--43948--7_81.

Index Terms

• Mathematics of computing

  • Probability and statistics

    • Probabilistic algorithms

    • Stochastic processes

      • Markov processes

• Theory of computation

  • Design and analysis of algorithms

    • Distributed algorithms

    • Parallel algorithms

  • Randomness, geometry and discrete structures

    • Random walks and Markov chains