Document Open Access Logo

Large Flocks of Small Birds: on the Minimal Size of Population Protocols

Authors Michael Blondin, Javier Esparza, Stefan Jaax

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.16.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Michael Blondin
Javier Esparza
Stefan Jaax

Cite As Get BibTex

Michael Blondin, Javier Esparza, and Stefan Jaax. Large Flocks of Small Birds: on the Minimal Size of Population Protocols. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.16

Abstract

Population protocols are a well established model of distributed computation by mobile finite-state agents with very limited storage. A classical result establishes that population protocols compute exactly predicates definable in Presburger arithmetic. We initiate the study of the minimal amount of memory required to compute a given predicate as a function of its size. We present results on the predicates x >= n for n \in N, and more generally on the predicates corresponding to systems of linear inequalities. We show that they can be computed by protocols with O(log n) states (or, more generally, logarithmic in the coefficients of the predicate), and that, surprisingly, some families of predicates can be computed by protocols with O(log log n) states. We give essentially matching lower bounds for the class of 1-aware protocols.

Subject Classification

Keywords
  • Population protocols
  • Presburger arithmetic

Metrics

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

References

  1. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. Time-space trade-offs in population protocols. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2560-2579. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.169.
  2. Dan Alistarh, Rati Gelashvili, and Milan Vojnovic. Fast and exact majority in population protocols. In Chryssis Georgiou and Paul G. Spirakis, editors, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 47-56. ACM, 2015. URL: http://dx.doi.org/10.1145/2767386.2767429.
  3. Dana Angluin, James Aspnes, Melody Chan, Michael J. Fischer, Hong Jiang, and René Peralta. Stably computable properties of network graphs. In Viktor K. Prasanna, S. Sitharama Iyengar, Paul G. Spirakis, and Matt Welsh, editors, Distributed Computing in Sensor Systems, First IEEE International Conference, DCOSS 2005, Marina del Rey, CA, USA, June 30 - July 1, 2005, Proceedings, volume 3560 of Lecture Notes in Computer Science, pages 63-74. Springer, 2005. URL: http://dx.doi.org/10.1007/11502593_8.
  4. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. In Soma Chaudhuri and Shay Kutten, editors, Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, July 25-28, 2004, pages 290-299. ACM, 2004. URL: http://dx.doi.org/10.1145/1011767.1011810.
  5. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183-199, 2008. URL: http://dx.doi.org/10.1007/s00446-008-0067-z.
  6. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007. URL: http://dx.doi.org/10.1007/s00446-007-0040-2.
  7. James Aspnes. Clocked population protocols. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 431-440. ACM, 2017. URL: http://dx.doi.org/10.1145/3087801.3087836.
  8. James Aspnes and Eric Ruppert. An introduction to population protocols. In Middleware for Network Eccentric and Mobile Applications, pages 97-120. Springer Berlin Heidelberg, 2009. URL: http://dx.doi.org/10.1007/978-3-540-89707-1_5.
  9. Andreas Bilke, Colin Cooper, Robert Elsässer, and Tomasz Radzik. Brief announcement: Population protocols for leader election and exact majority with O(log^2 n) states and O(log^2 n) convergence time. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 451-453. ACM, 2017. URL: http://dx.doi.org/10.1145/3087801.3087858.
  10. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. In Yoram Moses, editor, Distributed Computing - 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings, volume 9363 of Lecture Notes in Computer Science, pages 602-616. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48653-5_40.
  11. Javier Esparza, Pierre Ganty, Jérôme Leroux, and Rupak Majumdar. Verification of population protocols. Acta Inf., 54(2):191-215, 2017. URL: http://dx.doi.org/10.1007/s00236-016-0272-3.
  12. Alain Finkel and Jérôme Leroux. Recent and simple algorithms for petri nets. Software and System Modeling, 14(2):719-725, 2015. URL: http://dx.doi.org/10.1007/s10270-014-0426-0.
  13. Rachid Guerraoui and Eric Ruppert. Names trump malice: Tiny mobile agents can tolerate byzantine failures. In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas, and Wolfgang Thomas, editors, Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part II, volume 5556 of Lecture Notes in Computer Science, pages 484-495. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02930-1_40.
  14. Giuseppe Antonio Di Luna, Paola Flocchini, Taisuke Izumi, Tomoko Izumi, Nicola Santoro, and Giovanni Viglietta. Population protocols with faulty interactions: The impact of a leader. In Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, editors, Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings, volume 10236 of Lecture Notes in Computer Science, pages 454-466, 2017. URL: http://dx.doi.org/10.1007/978-3-319-57586-5_38.
  15. Ernst W. Mayr and Albert R. Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics, 46(3):305-329, 1982. URL: http://dx.doi.org/10.1016/0001-8708(82)90048-2.
  16. Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis. Mediated population protocols. Theor. Comput. Sci., 412(22):2434-2450, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.02.003.
  17. Charles Rackoff. The covering and boundedness problems for vector addition systems. Theor. Comput. Sci., 6:223-231, 1978. URL: http://dx.doi.org/10.1016/0304-3975(78)90036-1.
  18. David Soloveichik, Matthew Cook, Erik Winfree, and Jehoshua Bruck. Computation with finite stochastic chemical reaction networks. Natural Computing, 7(4):615-633, 2008. URL: http://dx.doi.org/10.1007/s11047-008-9067-y.
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