Fast Graphical Population Protocols

Authors Dan Alistarh, Rati Gelashvili, Joel Rybicki



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.14.pdf
  • Filesize: 0.91 MB
  • 18 pages

Document Identifiers

Author Details

Dan Alistarh
  • IST Austria, Klosterneuburg, Austria
Rati Gelashvili
  • Novi Research, Menlo Park, CA, USA
Joel Rybicki
  • IST Austria, Klosterneuburg, Austria

Acknowledgements

We grateful to Giorgi Nadiradze for pointing out a generalisation of the phase clock construction to non-regular graphs. We also thank anonymous reviewers for their useful comments on earlier versions of this manuscript.

Cite AsGet BibTex

Dan Alistarh, Rati Gelashvili, and Joel Rybicki. Fast Graphical Population Protocols. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.OPODIS.2021.14

Abstract

Let G be a graph on n nodes. In the stochastic population protocol model, a collection of n indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other’s states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when G is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in n polylog n pairwise interactions, with high probability, using at most polylog n states per node. In this work, we consider the more general setting where G is an arbitrary regular graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As a sample application, we show that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties. We believe our results will prove generally useful, as they allow efficient technology transfer between the well-mixed (clique) case, and the under-explored spatial setting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • population protocols
  • leader election
  • exact majority
  • graphs

Metrics

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

References

  1. David Aldous. Random walks on finite groups and rapidly mixing Markov chains. In Séminaire de Probabilités XVII 1981/82, pages 243-297. Springer, 1983. Google Scholar
  2. David Aldous and James Allen Fill. Reversible markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014, available at URL: http://www.stat.berkeley.edu/users/aldous/RWG/book.html.
  3. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L Rivest. Time-space trade-offs in population protocols. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 2560-2579, 2017. Google Scholar
  4. Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. In Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018). SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.144.
  5. Dan Alistarh and Rati Gelashvili. Recent algorithmic advances in population protocols. SIGACT News, 49(3):63-73, 2018. URL: https://doi.org/10.1145/3289137.3289150.
  6. Dan Alistarh, Rati Gelashvili, and Joel Rybicki. Fast graphical population protocols. Full version. URL: http://arxiv.org/abs/2102.08808.
  7. Dan Alistarh, Rati Gelashvili, and Milan Vojnović. Fast and exact majority in population protocols. In Proc. 34th ACM Symposium on Principles of Distributed Computing (PODC 2015), pages 47-56, 2015. Google Scholar
  8. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed computing, 18(4):235-253, 2006. Google Scholar
  9. Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. In Proc. 25th ACM Symposium on Principles of distributed computing (PODC 2006), pages 292-299, 2006. Google Scholar
  10. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183-199, 2008. URL: https://doi.org/10.1007/s00446-008-0067-z.
  11. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007. Google Scholar
  12. Dana Angluin, James Aspnes, Michael J Fischer, and Hong Jiang. Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 3(4):1-28, 2008. Google Scholar
  13. James Aspnes and Eric Ruppert. An introduction to population protocols. In Middleware for Network Eccentric and Mobile Applications, pages 97-120. Springer, 2009. Google Scholar
  14. Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM Journal on Computing, 29(1):180-200, 1999. Google Scholar
  15. Joffroy Beauquier, Peva Blanchard, and Janna Burman. Self-stabilizing leader election in population protocols over arbitrary communication graphs. In International Conference on Principles of Distributed Systems, pages 38-52. Springer, 2013. URL: https://hal.archives-ouvertes.fr/hal-00867287v2.
  16. Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. A population protocol for exact majority with O(log_5/3 n) stabilization time and Θ(log n) states. In Proc. 32nd International Symposium on Distributed Computing (DISC 2018), pages 10:1-10:18, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.10.
  17. Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, and Chris Wastell. Plurality consensus in arbitrary graphs: Lessons learned from load balancing. In Proc. 24th Annual European Symposium on Algorithms (ESA 2016), volume 57, pages 10:1-10:18, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.10.
  18. Petra Berenbrink, George Giakkoupis, and Peter Kling. Tight bounds for coalescing-branching random walks on regular graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1715-1733. SIAM, 2018. Google Scholar
  19. Petra Berenbrink, George Giakkoupis, and Peter Kling. Optimal time and space leader election in population protocols. In Proc. 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), pages 119-129, 2020. Google Scholar
  20. Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. Simple and efficient leader election. In Proc. 1st Symposium on Simplicity in Algorithms (SOSA 2018), pages 9:1-9:11, 2018. URL: https://doi.org/10.4230/OASIcs.SOSA.2018.9.
  21. Michael Blondin, Javier Esparza, and Stefan Jaax. Large flocks of small birds: on the minimal size of population protocols. In Proc. 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  22. Robert Brijder. Computing with chemical reaction networks: a tutorial. Natural Computing, 18(1):119-137, 2019. Google Scholar
  23. Pietro Caputo, Thomas M. Liggett, and Thomas Richthammer. Proof of Aldous' spectral gap conjecture. Journal of the American Mathematical Society, 23(3):831-851, 2010. Google Scholar
  24. Hsueh-Ping Chen and Ho-Lin Chen. Self-stabilizing leader election. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 53-59, 2019. Google Scholar
  25. Hsueh-Ping Chen and Ho-Lin Chen. Self-stabilizing leader election in regular graphs. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC '20, pages 210-217, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3382734.3405733.
  26. Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. Coalescing random walks and voting on connected graphs. SIAM Journal on Discrete Mathematics, 27(4):1748-1758, 2013. URL: https://doi.org/10.1137/120900368.
  27. Colin Cooper, Tomasz Radzik, Nicolás Rivera, and Takeharu Shiraga. Fast plurality consensus in regular expanders. In Proc. 31st International Symposium on Distributed Computing (DISC 2017), pages 13:1-13:16, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.13.
  28. Persi Diaconis and Laurent Saloff-Coste. Comparison techniques for random walk on finite groups. The Annals of Probability, 21(4):2131-2156, 1993. Google Scholar
  29. Persi Diaconis and Mehrdad Shahshahani. Generating a random permutation with random transpositions. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 57(2):159-179, 1981. Google Scholar
  30. AB Dieker. Interlacings for random walks on weighted graphs and the interchange process. SIAM Journal on Discrete Mathematics, 24(1):191-206, 2010. Google Scholar
  31. David Doty, Mahsa Eftekhari, Leszek Gąsieniec, Eric Severson, Grzegorz Stachowiak, and Przemysław Uznański. A time and space optimal stable population protocol solving exact majority. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.10201.
  32. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. Distributed Computing, 31(4):257-271, 2018. Google Scholar
  33. Moez Draief and Milan Vojnović. Convergence speed of binary interval consensus. SIAM Journal on Control and Optimization, 50(3):1087-1109, 2012. Google Scholar
  34. Robert Elsässer and Tomasz Radzik. Recent results in population protocols for exact majority and leader election. Bulletin of the EATCS, 126, 2018. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/549.
  35. Leszek Gąsiniec and Grzegorz Stachowiak. Fast space optimal leader election in population protocols. In Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 2018. URL: https://doi.org/10.1137/1.9781611975031.169.
  36. Leszek Gąsiniec, Grzegorz Stachowiak, and Przemyslaw Uznański. Almost logarithmic-time space optimal leader election in population protocols. In Proc. 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), 2019. URL: https://doi.org/10.1145/3323165.3323178.
  37. Leszek Gąsiniec, Grzegorz Stachowiak, and Przemyslaw Uznański. Time and space optimal exact majority population protocols, 2020. URL: http://arxiv.org/abs/2011.07392.
  38. Johan Jonasson. Mixing times for the interchange process. Latin American Journal of Probability and Mathematical Statistics, 9(2):667-683, 2012. Google Scholar
  39. Anissa Lamani and Masafumi Yamashita. Realization of periodic functions by self-stabilizing population protocols with synchronous handshakes. In International Conference on Theory and Practice of Natural Computing, pages 21-33. Springer, 2016. Google Scholar
  40. Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787-832, 1999. Google Scholar
  41. David A. Levin and Yuval Peres. Markov Chains and Mixing Times. American Mathematical Society, 2 edition, 2017. Google Scholar
  42. George B. Mertzios, Sotiris E. Nikoletseas, Christoforos Raptopoulos, and Paul G. Spirakis. Determining majority in networks with local interactions and very small local memory. In Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), pages 871-882, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_72.
  43. George B Mertzios, Sotiris E Nikoletseas, Christoforos L Raptopoulos, and Paul G Spirakis. Determining majority in networks with local interactions and very small local memory. Distributed Computing, 30(1):1-16, 2017. Google Scholar
  44. Yuval Peres, Kunal Talwar, and Udi Wieder. Graphical balanced allocations and the (1+β)-choice process. Random Structures and Algorithms, 47(4):760-775, 2014. URL: https://doi.org/10.1002/rsa.20558.
  45. Thomas Sauerwald and He Sun. Tight bounds for randomized load balancing on arbitrary network topologies. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pages 341-350, 2012. URL: https://doi.org/10.1109/FOCS.2012.86.
  46. Yuichi Sudo, Fukuhito Ooshita, Taisuke Izumi, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Logarithmic expected-time leader election in population protocol model. In Proc. International Symposium on Stabilizing, Safety, and Security of Distributed Systems (SSS 2019), pages 323-337, 2019. Google Scholar
  47. Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K Datta, and Lawrence L Larmore. Loosely-stabilizing leader election for arbitrary graphs in population protocol model. IEEE Transactions on Parallel and Distributed Systems, 30(6):1359-1373, 2018. Google Scholar
  48. Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, and Toshimitsu Masuzawa. Self-stabilizing population protocols with global knowledge. IEEE Transactions on Parallel and Distributed Systems, 2021. Google Scholar
  49. Alan M. Turing. The chemical basis of morphogenesis. Philosophical Transactions of the Royal Society of London, Series B, 237(641):37-72, 1952. Google Scholar
  50. David B. Wilson. Mixing times of lozenge tiling and card shuffling Markov chains. The Annals of Applied Probability, 14(1):274-325, 2004. Google Scholar
  51. Daisuke Yokota, Yuichi Sudo, and Toshimitsu Masuzawa. Time-optimal self-stabilizing leader election on rings in population protocols. In International Symposium on Stabilizing, Safety, and Security of Distributed Systems, pages 301-316. Springer, 2020. Google Scholar
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