Document Open Access Logo

Smoothed Analysis of Population Protocols

Authors Gregory Schwartzman, Yuichi Sudo

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.34.pdf
  • Filesize: 0.9 MB
  • 19 pages

Document Identifiers

Author Details

Gregory Schwartzman
  • JAIST, Nomi, Japan
Yuichi Sudo
  • Hosei University, Tokyo, Japan

Cite As Get BibTex

Gregory Schwartzman and Yuichi Sudo. Smoothed Analysis of Population Protocols. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.34

Abstract

In this work, we initiate the study of smoothed analysis of population protocols. We consider a population protocol model where an adaptive adversary dictates the interactions between agents, but with probability p every such interaction may change into an interaction between two agents chosen uniformly at random. That is, p-fraction of the interactions are random, while (1-p)-fraction are adversarial. The aim of our model is to bridge the gap between a uniformly random scheduler (which is too idealistic) and an adversarial scheduler (which is too strict).
We focus on the fundamental problem of leader election in population protocols. We show that, for a population of size n, the leader election problem can be solved in O(p^{-2}n log³ n) steps with high probability, using O((log² n) ⋅ (log (n/p))) states per agent, for all values of p ≤ 1. Although our result does not match the best known running time of O(n log n) for the uniformly random scheduler (p = 1), we are able to present a smooth transition between a running time of O(n polylog n) for p = 1 and an infinite running time for the adversarial scheduler (p = 0), where the problem cannot be solved. The key technical contribution of our work is a novel phase clock algorithm for our model. This is a key primitive for much-studied fundamental population protocol algorithms (leader election, majority), and we believe it is of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Population protocols
  • Smoothed analysis
  • Leader election

Metrics

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

Related Versions

References

  1. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L Rivest. Time-space trade-offs in population protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2560-2579. SIAM, 2017. Google Scholar
  2. Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2221-2239. SIAM, 2018. Google Scholar
  3. Dan Alistarh and Rati Gelashvili. Polylogarithmic-time leader election in population protocols. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, pages 479-491, 2015. Google Scholar
  4. D. Angluin, J. Aspnes, M. J Fischer, and H. Jiang. Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems, 3(4):13, 2008. Google Scholar
  5. 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
  6. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183-199, 2008. Google Scholar
  7. J. Beauquier, P. Blanchard, and J. Burman. Self-stabilizing leader election in population protocols over arbitrary communication graphs. In International Conference on Principles of Distributed Systems, pages 38-52, 2013. Google Scholar
  8. Joffroy Beauquier, Peva Blanchard, Janna Burman, and Rachid Guerraoui. The benefits of entropy in population protocols. In OPODIS, volume 46 of LIPIcs, pages 21:1-21:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. Google Scholar
  9. Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. Time-space trade-offs in population protocols for the majority problem. Distributed Computing, pages 1-21, 2020. Google Scholar
  10. Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. Time-space trade-offs in population protocols for the majority problem. Distributed Computing, pages 1-21, 2020. Google Scholar
  11. Petra Berenbrink, George Giakkoupis, and Peter Kling. Optimal time and space leader election in population protocols. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 119-129, 2020. Google Scholar
  12. Andreas Bilke, Colin Cooper, Robert Elsässer, and Tomasz Radzik. Brief announcement: Population protocols for leader election and exact majority with O(log² n) states and O(log² n) convergence time. In Proceedings of the 38th ACM Symposium on Principles of Distributed Computing, pages 451-453, 2017. Google Scholar
  13. Janna Burman, David Doty, Thomas Nowak, Eric E Severson, and Chuan Xu. Efficient self-stabilizing leader election in population protocols. arXiv preprint, 2019. URL: http://arxiv.org/abs/1907.06068.
  14. S. Cai, T. Izumi, and K. Wada. How to prove impossibility under global fairness: On space complexity of self-stabilizing leader election on a population protocol model. Theory of Computing Systems, 50(3):433-445, 2012. Google Scholar
  15. D. Canepa and M. G. Potop-Butucaru. Stabilizing leader election in population protocols, 2007. URL: http://hal.inria.fr/inria-00166632.
  16. Luca Cardelli and Attila Csikász-Nagy. The cell cycle switch computes approximate majority. Scientific reports, 2(1):1-9, 2012. Google Scholar
  17. Soumyottam Chatterjee, Gopal Pandurangan, and Nguyen Dinh Pham. Distributed MST: A smoothed analysis. In ICDCN, pages 15:1-15:10. ACM, 2020. Google Scholar
  18. Ho-Lin Chen, Rachel Cummings, David Doty, and David Soloveichik. Speed faults in computation by chemical reaction networks. Distributed Comput., 30(5):373-390, 2017. Google Scholar
  19. 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
  20. 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, pages 210-217, 2020. Google Scholar
  21. Yuan-Jyue Chen, Neil Dalchau, Niranjan Srinivas, Andrew Phillips, Luca Cardelli, David Soloveichik, and Georg Seelig. Programmable chemical controllers made from dna. Nature nanotechnology, 8(10):755-762, 2013. Google Scholar
  22. Michael Dinitz, Jeremy T Fineman, Seth Gilbert, and Calvin Newport. Smoothed analysis of dynamic networks. Distributed Computing, 31(4):273-287, 2018. Google Scholar
  23. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. Distributed Computing, 31(4):257-271, 2018. Google Scholar
  24. Moez Draief and Milan Vojnovic. Convergence speed of binary interval consensus. SIAM J. Control. Optim., 50(3):1087-1109, 2012. Google Scholar
  25. M. J. Fischer and H. Jiang. Self-stabilizing leader election in networks of finite-state anonymous agents. In International Conference on Principles of Distributed Systems, pages 395-409, 2006. URL: https://doi.org/10.1007/11945529_28.
  26. Leszek Gąsieniec and Grzegorz Stachowiak. Enhanced phase clocks, population protocols, and fast space optimal leader election. Journal of the ACM (JACM), 68(1):1-21, 2020. Google Scholar
  27. Leszek Gąsieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. Almost logarithmic-time space optimal leader election in population protocols. In The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, pages 93-102. ACM, 2019. Google Scholar
  28. Uri Meir, Ami Paz, and Gregory Schwartzman. Models of smoothing in dynamic networks. In DISC, volume 179 of LIPIcs, pages 36:1-36:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  29. Othon Michail, Paul G Spirakis, and Michail Theofilatos. Simple and fast approximate counting and leader election in populations. In Proceedings of the 20th International Symposium on Stabilizing, Safety, and Security of Distributed Systems, pages 154-169, 2018. Google Scholar
  30. Anisur Rahaman Molla and Disha Shur. Smoothed analysis of leader election in distributed networks. In SSS, volume 12514 of Lecture Notes in Computer Science, pages 183-198. Springer, 2020. Google Scholar
  31. Etienne Perron, Dinkar Vasudevan, and Milan Vojnovic. Using three states for binary consensus on complete graphs. In INFOCOM, pages 2527-2535. IEEE, 2009. Google Scholar
  32. Ryoya Sadano, Yuichi Sudo, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. A population protocol model with interaction probability considering speeds of agents. In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), pages 2113-2122. IEEE, 2019. Google Scholar
  33. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385-463, 2004. Google Scholar
  34. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM, 52(10):76-84, 2009. Google Scholar
  35. Yuichi Sudo, Ryota Eguchi, Taisuke Izumi, and Toshimitsu Masuzawa. Time-optimal loosely-stabilizing leader election in population protocols. arXiv preprint, 2020. URL: http://arxiv.org/abs/2005.09944.
  36. Yuichi Sudo and Toshimitsu Masuzawa. Leader election requires logarithmic time in population protocols. Parallel Processing Letters, 30(01):2050005, 2020. Google Scholar
  37. Yuichi Sudo, Junya Nakamura, Yukiko Yamauchi, Fukuhito Ooshita, Hirotsugu. Kakugawa, and Toshimitsu Masuzawa. Loosely-stabilizing leader election in a population protocol model. Theoretical Computer Science, 444:100-112, 2012. Google Scholar
  38. Yuichi Sudo, Fukuhito Ooshita, Taisuke Izumi, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Time-optimal leader election in population protocols. IEEE Trans. Parallel Distributed Syst., 31(11):2620-2632, 2020. Google Scholar
  39. Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K Datta, and Lawrence L Larmore. Loosely-stabilizing leader election with polylogarithmic convergence time. Theoretical Computer Science, 806:617-631, 2020. Google Scholar
  40. 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, (Early Access):1-13, 2021. URL: https://doi.org/10.1109/TPDS.2021.3076769.
  41. Chuan Xu, Joffroy Beauquier, Janna Burman, Shay Kutten, and Thomas Nowak. Data collection in population protocols with non-uniformly random scheduler. Theor. Comput. Sci., 806:516-530, 2020. Google Scholar
  42. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact