Balanced Allocation on Dynamic Hypergraphs

Authors Catherine Greenhill, Bernard Mans, Ali Pourmiri



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.11.pdf
  • Filesize: 0.58 MB
  • 22 pages

Document Identifiers

Author Details

Catherine Greenhill
  • UNSW Sydney, Australia
Bernard Mans
  • Macquarie University, Sydney, Australia
Ali Pourmiri
  • Macquarie University, Sydney, Australia

Cite AsGet BibTex

Catherine Greenhill, Bernard Mans, and Ali Pourmiri. Balanced Allocation on Dynamic Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.11

Abstract

The {balls-into-bins model} randomly allocates n sequential balls into n bins, as follows: each ball selects a set D of d ⩾ 2 bins, independently and uniformly at random, then the ball is allocated to a least-loaded bin from D (ties broken randomly). The maximum load is the maximum number of balls in any bin. In 1999, Azar et al. showed that, provided ties are broken randomly, after n balls have been placed the maximum load, is log_d log n + 𝒪(1), with high probability. We consider this popular paradigm in a dynamic environment where the bins are structured as a dynamic hypergraph. A dynamic hypergraph is a sequence of hypergraphs, say ℋ^(t), arriving over discrete times t = 1,2,…, such that the vertex set of ℋ^(t)’s is the set of n bins, but (hyper)edges may change over time. In our model, the t-th ball chooses an edge from ℋ^(t) uniformly at random, and then chooses a set D of d ⩾ 2 random bins from the selected edge. The ball is allocated to a least-loaded bin from D, with ties broken randomly. We quantify the dynamicity of the model by introducing the notion of pair visibility, which measures the number of rounds in which a pair of bins appears within a (hyper)edge. We prove that if, for some ε > 0, a dynamic hypergraph has pair visibility at most n^{1-ε}, and some mild additional conditions hold, then with high probability the process has maximum load 𝒪(log_dlog n). Our proof is based on a variation of the witness tree technique, which is of independent interest. The model can also be seen as an adversarial model where an adversary decides the structure of the possible sets of d bins available to each ball.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • balls-into-bins
  • balanced allocation
  • power of two choices
  • witness tree technique

Metrics

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

References

  1. Anders Aamand, Mathias Bæk Tejs Knudsen, and Mikkel Thorup. Power of d choices with simple tabulation. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 5:1-5:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.5.
  2. 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.
  3. Petra Berenbrink, André Brinkmann, Tom Friedetzky, and Lars Nagel. Balls into bins with related random choices. J. Parallel Distrib. Comput., 72(2):246-253, 2012. Google Scholar
  4. Paul Bogdan, Thomas Sauerwald, Alexandre Stauffer, and He Sun. Balls into bins via local search. In Proc. 24th Symp. Discrete Algorithms (SODA), pages 16-34, 2013. Google Scholar
  5. John W. Byers, Jeffrey Considine, and Michael Mitzenmacher. Geometric generalizations of the power of two choices. In Proc. 16th Symp. Parallelism in Algorithms and Architectures (SPAA), pages 54-63, 2004. Google Scholar
  6. L. Elisa Celis, Omer Reingold, Gil Segev, and Udi Wieder. Balls and bins: Smaller hash families and faster evaluation. SIAM J. Comput., 42(3):1030-1050, 2013. URL: https://doi.org/10.1137/120871626.
  7. Xue Chen. Derandomized balanced allocation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2513-2526, 2019. URL: https://doi.org/10.1137/1.9781611975482.154.
  8. Kai-Min Chung, Henry Lam, Zhenming Liu, and Michael Mitzenmacher. Chernoff-hoeffding bounds for markov chains: Generalized and simplified. In 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France, pages 124-135, 2012. URL: https://doi.org/10.4230/LIPIcs.STACS.2012.124.
  9. Andrea E. F. Clementi, Angelo Monti, Francesco Pasquale, and Riccardo Silvestri. Information spreading in stationary markovian evolving graphs. IEEE Trans. Parallel Distrib. Syst., 22(9):1425-1432, 2011. URL: https://doi.org/10.1109/TPDS.2011.33.
  10. Xavier Dahan. Regular graphs of large girth and arbitrary degree. Combinatorica, 34(4):407-426, 2014. Google Scholar
  11. Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, and Mikkel Thorup. The power of two choices with simple tabulation. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’16, page 1631–1642, USA, 2016. Society for Industrial and Applied Mathematics. Google Scholar
  12. Brighten Godfrey. Balls and bins with structure: balanced allocations on hypergraphs. In Proc. 19th Symp. Discrete Algorithms (SODA), pages 511-517, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347138.
  13. Krishnaram Kenthapadi and Rina Panigrahy. Balanced allocation on graphs. In Proc. 17th Symp. Discrete Algorithms (SODA), pages 434-443, 2006. Google Scholar
  14. Donald Knuth. The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Adison-Wesley, third edition, 1997. Google Scholar
  15. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, 2006. URL: http://scholar.google.com/scholar.bib?q=info:3wf9IU94tyMJ:scholar.google.com/&output=citation&hl=en&as_sdt=2000&ct=citation&cd=0.
  16. Michael Mitzenmacher, Andréa W. Richa, and Ramesh Sitaraman. The power of two random choices: A survey of techniques and results. In in Handbook of Randomized Computing, pages 255-312. Kluwer, 2000. Google Scholar
  17. Yuval Peres, Kunal Talwar, and Udi Wieder. Graphical balanced allocations and the (1 + β)-choice process. Random Struct. Algorithms, DOI: 10.1002/rsa.20558, 2014. Google Scholar
  18. Ali Pourmiri. Balanced allocation on graphs: A random walk approach. Random Struct. Algorithms, 55(4):980-1009, 2019. URL: https://doi.org/10.1002/rsa.20875.
  19. N. J. A. Sloane. Oeis foundation inc., the on-line encyclopedia of integer sequences, 1964. URL: http://oeis.org/A000108.
  20. Berthold Vöcking. How asymmetry helps load balancing. J. ACM, 50(4):568-589, 2003. URL: https://doi.org/10.1145/792538.792546.
  21. Udi Wieder. Hashing, load balancing and multiple choice. Foundations and Trends in Theoretical Computer Science, 12(3-4):275-379, 2017. URL: https://doi.org/10.1561/0400000070.
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