Document Open Access Logo

Dynamic Size Counting in Population Protocols

Authors David Doty , Mahsa Eftekhari

PDF
Thumbnail PDF

File

LIPIcs.SAND.2022.13.pdf
  • Filesize: 0.84 MB
  • 18 pages

Document Identifiers

Author Details

David Doty
  • University of California, Davis, CA, USA
Mahsa Eftekhari
  • University of California, Davis, CA, USA

Funding

Supported by NSF award 1900931 and CAREER award 1844976.

Cite As Get BibTex

David Doty and Mahsa Eftekhari. Dynamic Size Counting in Population Protocols. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SAND.2022.13

Abstract

The population protocol model describes a network of anonymous agents that interact asynchronously in pairs chosen at random. Each agent starts in the same initial state s. We introduce the dynamic size counting problem: approximately counting the number of agents in the presence of an adversary who at any time can remove any number of agents or add any number of new agents in state s. A valid solution requires that after each addition/removal event, resulting in population size n, with high probability each agent "quickly" computes the same constant-factor estimate of the value log₂(n) (how quickly is called the convergence time), which remains the output of every agent for as long as possible (the holding time). Since the adversary can remove agents, the holding time is necessarily finite: even after the adversary stops altering the population, it is impossible to stabilize to an output that never again changes.
We first show that a protocol solves the dynamic size counting problem if and only if it solves the loosely-stabilizing counting problem: that of estimating log n in a fixed-size population, but where the adversary can initialize each agent in an arbitrary state, with the same convergence time and holding time. We then show a protocol solving the loosely-stabilizing counting problem with the following guarantees: if the population size is n, M is the largest initial estimate of log n, and s is the maximum integer initially stored in any field of the agents' memory, we have expected convergence time O(log n + log M), expected polynomial holding time, and expected memory usage of O(log²(s) + (log log n)²) bits. Interpreted as a dynamic size counting protocol, when changing from population size n_prev to n_next, the convergence time is O(log n_next + log log n_prev).

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Models of computation
Keywords
  • Loosely-stabilizing
  • population protocols
  • size counting

Metrics

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

Related Versions

Supplementary Materials

References

  1. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L Rivest. Time-space trade-offs in population protocols. In SODA 2017: 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 SODA 2018: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2221-2239. SIAM, 2018. Google Scholar
  3. Dan Alistarh, Bartłomiej Dudek, Adrian Kosowski, David Soloveichik, and Przemysław Uznański. Robust detection in leak-prone population protocols. In DNA Computing and Molecular Programming, pages 155-171. Springer International Publishing, 2017. Google Scholar
  4. Dan Alistarh and Rati Gelashvili. Polylogarithmic-time leader election in population protocols. In ICALP 2015: Proceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming - Volume 9135, pages 479-491. Springer-Verlag, 2015. URL: https://doi.org/10.1007/978-3-662-47666-6_38.
  5. Dan Alistarh, Martin Töpfer, and Przemysław Uznański. Fast and robust comparison in population protocols. In PODC 2021: The ACM Symposium on Principles of Distributed Computing, 2021. Google Scholar
  6. 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
  7. Dana Angluin, James Aspnes, Michael J. Fischer, and Hong Jiang. Self-stabilizing population protocols. ACM Trans. Auton. Adapt. Syst., 3(4):1-28, 2008. URL: https://doi.org/10.1145/1452001.1452003.
  8. James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier. Time and space optimal counting in population protocols. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016), volume 70, pages 13:1-13:17, 2017. Google Scholar
  9. Joffroy Beauquier, Janna Burman, Simon Clavière, and Devan Sohier. Space-optimal counting in population protocols. In Distributed Computing, pages 631-646, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. Google Scholar
  10. Joffroy Beauquier, Julien Clement, Stephane Messika, Laurent Rosaz, and Brigitte Rozoy. Self-stabilizing counting in mobile sensor networks with a base station. In Distributed Computing, pages 63-76, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  11. Stav Ben-Nun, Tsvi Kopelowitz, Matan Kraus, and Ely Porat. An O(log^3/2 n) parallel time population protocol for majority with O(log n) states. In PODC 2020: Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 191-199. Association for Computing Machinery, 2020. URL: https://doi.org/10.1145/3382734.3405747.
  12. Petra Berenbrink, Felix Biermeier, Christopher Hahn, and Dominik Kaaser. Loosely-stabilizing phase clocks and the adaptive majority problem. In SAND 2021: 1st Symposium on Algorithmic Foundations of Dynamic Networks, 2021. Google Scholar
  13. 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 Theta(log n) States. In 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1-10:18, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.10.
  14. 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, STOC 2020, pages 119-129, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3357713.3384312.
  15. Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. Simple and efficient leader election. In SOSA 2018: The 1st Symposium on Simplicity in Algorithms, pages 9:1-9:11, 2018. URL: https://doi.org/10.4230/OASIcs.SOSA.2018.9.
  16. 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 PODC 2017: Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 451-453. Association for Computing Machinery, 2017. URL: https://doi.org/10.1145/3087801.3087858.
  17. Janna Burman, Ho-Lin Chen, Hsueh-Ping Chen, David Doty, Thomas Nowak, Eric Severson, and Chuan Xu. Time-optimal self-stabilizing leader election in population protocols. In PODC 2021: Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 33-44. ACM, 2021. URL: https://doi.org/10.1145/3465084.3467898.
  18. David Doty and Mahsa Eftekhari. Efficient size estimation and impossibility of termination in uniform dense population protocols. In PODC 2019: Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 34-42. Association for Computing Machinery, 2019. URL: https://doi.org/10.1145/3293611.3331627.
  19. David Doty and Mahsa Eftekhari. A survey of size counting in population protocols. Theoretical Computer Science, 894:91-102, 2021. Building Bridges – Honoring Nataša Jonoska on the Occasion of Her 60th Birthday. URL: https://doi.org/10.1016/j.tcs.2021.08.038.
  20. David Doty and Mahsa Eftekhari. Dynamic size counting in population protocols, 2022. URL: http://arxiv.org/abs/2202.12864.
  21. David Doty, Mahsa Eftekhari, Othon Michail, Paul G. Spirakis, and Michail Theofilatos. Brief Announcement: Exact Size Counting in Uniform Population Protocols in Nearly Logarithmic Time. In 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1-46:3, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.46.
  22. Bartłomiej Dudek and Adrian Kosowski. Universal protocols for information dissemination using emergent signals. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 87-99, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3188745.3188818.
  23. Philippe Flajolet and G Nigel Martin. Probabilistic counting algorithms for data base applications. Journal of computer and system sciences, 31(2):182-209, 1985. Google Scholar
  24. Leszek Gasieniec, Grzegorz Stachowiak, and Przemysław Uznański. Almost logarithmic-time space optimal leader election in population protocols. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '19, pages 93-102. Association for Computing Machinery, 2019. URL: https://doi.org/10.1145/3323165.3323178.
  25. Shafi Goldwasser, Rafail Ostrovsky, Alessandra Scafuro, and Adam Sealfon. Population stability: regulating size in the presence of an adversary. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 397-406. ACM, 2018. Google Scholar
  26. Taisuke Izumi. On space and time complexity of loosely-stabilizing leader election. In Structural Information and Communication Complexity, pages 299-312. Springer International Publishing, 2015. Google Scholar
  27. Tomoko Izumi, Keigo Kinpara, Taisuke Izumi, and Koichi Wada. Space-efficient self-stabilizing counting population protocols on mobile sensor networks. Theoretical Computer Science, 552:99-108, 2014. URL: https://doi.org/10.1016/j.tcs.2014.07.028.
  28. Guy Louchard and Helmut Prodinger. The moments problem of extreme-value related distribution functions. Algorithmica, 2004. Google Scholar
  29. Guy Louchard, Helmut Prodinger, and Mark Daniel Ward. The number of distinct values of some multiplicity in sequences of geometrically distributed random variables. In Discrete Mathematics and Theoretical Computer Science, pages 231-256. Discrete Mathematics and Theoretical Computer Science, 2005. Google Scholar
  30. László Lovász and Peter Winkler. Reversal of markov chains and the forget time. Combinatorics, Probability and Computing, 7(2):189-204, 1998. Google Scholar
  31. Yves Mocquard, Emmanuelle Anceaume, James Aspnes, Yann Busnel, and Bruno Sericola. Counting with population protocols. In 14th IEEE International Symposium on Network Computing and Applications, pages 35-42, 2015. Google Scholar
  32. Helmut Prodinger. Philippe flajolet’s early work in combinatorics. arXiv preprint, 2021. URL: http://arxiv.org/abs/2103.15791.
  33. Yuichi Sudo, Ryota Eguchi, Taisuke Izumi, and Toshimitsu Masuzawa. Time-optimal loosely-stabilizing leader election in population protocols. In DISC 2021: The 35th International Symposium on Distributed Computing, 2021. Google Scholar
  34. Yuichi Sudo, Junya Nakamura, Yukiko Yamauchi, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely-stabilizing leader election in population protocol model. In Structural Information and Communication Complexity, pages 295-308, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  35. Yuichi Sudo, Fukuhito Ooshita, Taisuke Izumi, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Logarithmic expected-time leader election in population protocol model. In Stabilization, Safety, and Security of Distributed Systems, pages 323-337. Springer International Publishing, 2019. Google Scholar
  36. Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K. Datta, and Lawrence L. Larmore. Loosely-Stabilizing Leader Election with Polylogarithmic Convergence Time. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), volume 125 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1-30:16, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2018.30.
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