Document Open Access Logo

Message Complexity of Population Protocols

Authors Talley Amir, James Aspnes, David Doty , Mahsa Eftekhari, Eric Severson

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.6.pdf
  • Filesize: 0.66 MB
  • 18 pages

Document Identifiers

Author Details

Talley Amir
  • Yale University, New Haven, CT, USA
James Aspnes
  • Yale University, New Haven, CT, USA
David Doty
  • University of California, Davis, CA, USA
Mahsa Eftekhari
  • University of California, Davis, CA, USA
Eric Severson
  • University of California, Davis, CA, USA

Funding

The second author was supported by NSF award CCF-1650596. The third, fourth, and fifth authors were supported by NSF awards 1619343, 1844976, 1900931.

Cite AsGet BibTex

Talley Amir, James Aspnes, David Doty, Mahsa Eftekhari, and Eric Severson. Message Complexity of Population Protocols. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.6

Abstract

The standard population protocol model assumes that when two agents interact, each observes the entire state of the other. We initiate the study of message complexity for population protocols, where an agent’s state is divided into an externally-visible message and externally-hidden local state. We consider the case of O(1) message complexity. When time is unrestricted, we obtain an exact characterization of the stably computable predicates based on the number of internal states s(n): If s(n) = o(n) then the protocol computes semilinear predicates (unlike the original model, which can compute non-semilinear predicates with s(n) = O(log n)), and otherwise it computes a predicate decidable by a nondeterministic O(n log s(n))-space-bounded Turing machine. We then introduce novel O(polylog(n)) expected time protocols for junta/leader election and general purpose broadcast correct with high probability, and approximate and exact population size counting correct with probability 1. Finally, we show that the main constraint on the power of bounded-message-size protocols is the size of the internal states: with unbounded internal states, any computable function can be computed with probability 1 in the limit by a protocol that uses only 1-bit messages.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • population protocol
  • message complexity
  • space-optimal

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 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 International Colloquium on Automata, Languages, and Programming, pages 479-491. Springer, 2015. Google Scholar
  4. Dan Alistarh, Rati Gelashvili, and Milan Vojnović. Fast and exact majority in population protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 47-56, 2015. Google Scholar
  5. Dana Angluin, James Aspnes, and Dongqu Chen. A population protocol for binary signaling consensus. Technical Report YALEU/DCS/TR-1527, Yale University Department of Computer Science, 2016. 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, pages 235-253, March 2006. Google Scholar
  7. Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC ’06, page 292–299, New York, NY, USA, 2006. Association for Computing Machinery. URL: https://doi.org/10.1145/1146381.1146425.
  8. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183-199, September 2008. Google Scholar
  9. Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2):87-102, July 2008. Google Scholar
  10. James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier. Time and Space Optimal Counting in Population Protocols. In Panagiota Fatourou, Ernesto Jiménez, and Fernando Pedone, editors, 20th International Conference on Principles of Distributed Systems (OPODIS 2016), volume 70 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1-13:17, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2016.13.
  11. Amanda Belleville, David Doty, and David Soloveichik. Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols. In ICALP 2017: 44th International Colloquium on Automata, Languages, and Programming, volume 80, pages 141:1-141:14, 2017. Google Scholar
  12. Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. Majority & stabilization in population protocols. arXiv preprint arXiv:1805.04586, 2018. 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 Θ(log n) states. In 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  14. Petra Berenbrink, Tom Friedetzky, Dominik Kaaser, and Peter Kling. Tight & simple load balancing. In 2019 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019, Rio de Janeiro, Brazil, May 20-24, 2019, pages 718-726. IEEE, 2019. Google Scholar
  15. Petra Berenbrink, George Giakkoupis, and Peter Kling. Optimal time and space leader election in population protocols. In STOC 2020: 52nd Annual ACM Symposium on Theory of Computing, 2020. to appear. Google Scholar
  16. Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. Simple and efficient leader election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  17. Petra Berenbrink, Dominik Kaaser, and Tomasz Radzik. On counting the population size. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 43-52. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331631.
  18. 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 ACM Symposium on Principles of Distributed Computing, pages 451-453, 2017. Google Scholar
  19. Janna Burman, David Doty, Thomas Nowak, Eric E Severson, and Chuan Xu. Efficient self-stabilizing leader election in population protocols. arXiv preprint arXiv:1907.06068, 2019. Google Scholar
  20. Ioannis Chatzigiannakis, Othon Michail, Stavros Nikolaou, Andreas Pavlogiannis, and Paul G. Spirakis. Passively mobile communicating machines that use restricted space. In Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing, FOMC ’11, page 6–15, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/1998476.1998480.
  21. Ho-Lin Chen, David Doty, and David Soloveichik. Deterministic function computation with chemical reaction networks. Natural Computing, 13(4):517-534, 2014. Special issue of invited papers from DNA 2012. URL: https://doi.org/10.1007/s11047-013-9393-6.
  22. 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
  23. L. H. Diakite and L. Yu. Energy and bandwidth efficient wireless sensor communications for improving the energy efficiency of the air interface for wireless sensor networks. In 2013 IEEE Third International Conference on Information Science and Technology (ICIST), pages 1426-1429, March 2013. URL: https://doi.org/10.1109/ICIST.2013.6747805.
  24. David Doty. Timing in chemical reaction networks. In SODA 2014: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 772-784. SIAM, 2014. Google Scholar
  25. David Doty and Mahsa Eftekhari. Efficient size estimation and impossibility of termination in uniform dense population protocols. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 34-42. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331627.
  26. 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 DISC 2018: 32nd International Symposium on Distributed Computing, 2018. Google Scholar
  27. David Doty and Monir Hajiaghayi. Leaderless deterministic chemical reaction networks. Natural Computing, 14(2):213-223, 2015. Preliminary version appeared in DNA 2013. Google Scholar
  28. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. Distributed Computing, 31(4):257-271, 2018. Special issue of invited papers from DISC 2015. Google Scholar
  29. R. Elsässer and T. 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/546.
  30. Leszek Gasieniec and Grzegorz Stachowiak. Fast space optimal leader election in population protocols. In SODA, pages 2653-2667, 2018. URL: https://doi.org/10.1137/1.9781611975031.169.
  31. Leszek Gasieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. Almost logarithmic-time space optimal leader election in population protocols. In SPAA, pages 93-102, 2019. URL: https://doi.org/10.1145/3323165.3323178.
  32. Adrian Kosowski and Przemysław Uznański. Brief announcement: Population protocols are fast. In PODC, pages 475-477, 2018. URL: https://dl.acm.org/citation.cfm?id=3212788.
  33. R. Lu, X. Lin, H. Zhu, X. Liang, and X. Shen. Becan: A bandwidth-efficient cooperative authentication scheme for filtering injected false data in wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems, 23(1):32-43, January 2012. URL: https://doi.org/10.1109/TPDS.2011.95.
  34. Y. Mocquard, E. Anceaume, and B. Sericola. Optimal proportion computation with population protocols. In 2016 IEEE 15th International Symposium on Network Computing and Applications (NCA), pages 216-223, October 2016. Google Scholar
  35. 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
  36. E. Perron, D. Vasudevan, and M. Vojnovic. Using three states for binary consensus on complete graphs. In IEEE INFOCOM 2009, pages 2527-2535, April 2009. URL: https://doi.org/10.1109/INFCOM.2009.5062181.
  37. Lulu Qian, David Soloveichik, and Erik Winfree. Efficient Turing-universal computation with DNA polymers. In DNA 2010: Proceedings of The Sixteenth International Meeting on DNA Computing and Molecular Programming, volume 6518 of Lecture Notes in Computer Science. Springer, 2010. Google Scholar
  38. D. Soloveichik, M. Cook, E. Winfree, and J. Bruck. Computation with finite stochastic chemical reaction networks. Natural Computing, 7:615-633, 2008. Google Scholar
  39. David Soloveichik, Georg Seelig, and Erik Winfree. DNA as a universal substrate for chemical kinetics. In DNA14, pages 57-69, 2008. URL: https://doi.org/10.1007/978-3-642-03076-5_6.
  40. Niranjan Srinivas, James Parkin, Georg Seelig, Erik Winfree, and David Soloveichik. Enzyme-free nucleic acid dynamical systems. Science, 358(6369):eaal2052, 2017. Google Scholar
  41. Yuichi Sudo, Fukuhito Ooshita, Taisuke Izumi, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Logarithmic expected-time leader election in population protocol model. In International Symposium on Stabilizing, Safety, and Security of Distributed Systems, pages 323-337. Springer, 2019. Google Scholar
  42. P. Udayakumar, R. Vyas, and O. P. Vyas. Energy efficient election protocol for wireless sensor networks. In 2013 International Conference on Circuits, Power and Computing Technologies (ICCPCT), pages 1028-1033, March 2013. URL: https://doi.org/10.1109/ICCPCT.2013.6529026.
  43. Damien Woods, David Doty, Cameron Myhrvold, Joy Hui, Felix Zhou, Peng Yin, and Erik Winfree. Diverse and robust molecular algorithms using reprogrammable DNA self-assembly. Nature, 567:366-372, 2019. URL: https://doi.org/10.1038/s41586-019-1014-9.
  44. Bernard Yurke, Andrew J. Turberfield, Allen P. Mills, Jr., Friedrich C. Simmel, and Jennifer L. Nuemann. A DNA-fuelled molecular machine made of DNA. Nature, 406:605-608, 2000. 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 Imprint Privacy Contact