Fast and Succinct Population Protocols for Presburger Arithmetic

Authors Philipp Czerner , Roland Guttenberg , Martin Helfrich , Javier Esparza



PDF
Thumbnail PDF

File

LIPIcs.SAND.2022.11.pdf
  • Filesize: 0.76 MB
  • 17 pages

Document Identifiers

Author Details

Philipp Czerner
  • Department of Informatics, Technische Universität München, Germany
Roland Guttenberg
  • Department of Informatics, Technische Universität München, Germany
Martin Helfrich
  • Department of Informatics, Technische Universität München, Germany
Javier Esparza
  • Department of Informatics, Technische Universität München, Germany

Acknowledgements

We thank the anonymous reviewers for many helpful remarks. In particular, one remark led to Lemma 11, which in turn led to a nicer formulation of Theorem 2, one of our main results.

Cite AsGet BibTex

Philipp Czerner, Roland Guttenberg, Martin Helfrich, and Javier Esparza. Fast and Succinct Population Protocols for Presburger Arithmetic. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SAND.2022.11

Abstract

In their 2006 seminal paper in Distributed Computing, Angluin et al. present a construction that, given any Presburger predicate as input, outputs a leaderless population protocol that decides the predicate. The protocol for a predicate of size m (when expressed as a Boolean combination of threshold and remainder predicates with coefficients in binary) runs in 𝒪(m ⋅ n² log n) expected number of interactions, which is almost optimal in n, the number of interacting agents. However, the number of states of the protocol is exponential in m. This is a problem for natural computing applications, where a state corresponds to a chemical species and it is difficult to implement protocols with many states. Blondin et al. described in STACS 2020 another construction that produces protocols with a polynomial number of states, but exponential expected number of interactions. We present a construction that produces protocols with 𝒪(m) states that run in expected 𝒪(m⁷ ⋅ n²) interactions, optimal in n, for all inputs of size Ω(m). For this, we introduce population computers, a carefully crafted generalization of population protocols easier to program, and show that our computers for Presburger predicates can be translated into fast and succinct population protocols.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • population protocols
  • fast
  • succinct
  • population computers

Metrics

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

References

  1. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. Time-space trade-offs in population protocols. In SODA, pages 2560-2579. SIAM, 2017. Google Scholar
  2. Dan Alistarh and Rati Gelashvili. Recent algorithmic advances in population protocols. SIGACT News, 49(3):63-73, 2018. Google Scholar
  3. Dan Alistarh, Rati Gelashvili, and Milan Vojnovic. Fast and exact majority in population protocols. In PODC, pages 47-56. ACM, 2015. Google Scholar
  4. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. In PODC, pages 290-299. ACM, 2004. 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 Comput., 18(4):235-253, 2006. Google Scholar
  6. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Comput., 21(3):183-199, 2008. Google Scholar
  7. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Comput., 20(4):279-304, 2007. Google Scholar
  8. Michael Blondin, Javier Esparza, Blaise Genest, Martin Helfrich, and Stefan Jaax. Succinct population protocols for Presburger arithmetic. In STACS, volume 154 of LIPIcs, pages 40:1-40:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  9. Michael Blondin, Javier Esparza, and Stefan Jaax. Large flocks of small birds: On the minimal size of population protocols. In STACS, volume 96 of LIPIcs, pages 16:1-16:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  10. Robert Brijder, David Doty, and David Soloveichik. Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks. Natural Computing, 17(1):97-108, 2018. Google Scholar
  11. Philipp Czerner, Roland Guttenberg, Martin Helfrich, and Javier Esparza. Fast and succinct population protocols for Presburger arithmetic, 2022. URL: http://arxiv.org/abs/2202.11601.
  12. David Doty, Mahsa Eftekhari, Leszek Gasieniec, Eric E. Severson, Grzegorz Stachowiak, and Przemyslaw Uznanski. Brief announcement: A time and space optimal stable population protocol solving exact majority. In PODC, pages 77-80. ACM, 2021. Google Scholar
  13. Robert Elsässer and Tomasz Radzik. Recent results in population protocols for exact majority and leader election. Bull. EATCS, 126, 2018. Google Scholar
  14. Christoph Haase. A survival guide to Presburger arithmetic. ACM SIGLOG News, 5(3):67-82, 2018. 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