Document Open Access Logo

Expressive Power of Broadcast Consensus Protocols

Authors Michael Blondin, Javier Esparza, Stefan Jaax

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2019.31.pdf
  • Filesize: 0.58 MB
  • 16 pages

Document Identifiers

Author Details

Michael Blondin
  • Département d'informatique, Université de Sherbrooke, Sherbrooke, Canada
Javier Esparza
  • Fakultät für Informatik, Technische Universität München, Garching bei München, Germany
Stefan Jaax
  • Fakultät für Informatik, Technische Universität München, Garching bei München, Germany

Funding

  • Blondin, Michael: Supported by the Fonds de recherche du Québec – Nature et technologies (FRQNT), by a Quebec - Bavaria project funded by the Fonds de recherche du Québec (FRQ), and by the Natural Sciences and Engineering Research Council of Canada (NSERC).
  • Esparza, Javier: Supported by an ERC Advanced Grant (787367: PaVeS).
  • Jaax, Stefan: Supported by an ERC Advanced Grant (787367: PaVeS).

Acknowledgements

Part of this work was realized while Stefan Jaax was visiting the Université de Sherbrooke. We warmly thank the anonymous reviewers for their helpful comments and suggestions.

Cite AsGet BibTex

Michael Blondin, Javier Esparza, and Stefan Jaax. Expressive Power of Broadcast Consensus Protocols. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.CONCUR.2019.31

Abstract

Population protocols are a formal model of computation by identical, anonymous mobile agents interacting in pairs. Their computational power is rather limited: Angluin et al. have shown that they can only compute the predicates over N^k expressible in Presburger arithmetic. For this reason, several extensions of the model have been proposed, including the addition of devices called cover-time services, absence detectors, and clocks. All these extensions increase the expressive power to the class of predicates over N^k lying in the complexity class NL when the input is given in unary. However, these devices are difficult to implement, since they require that an agent atomically receives messages from all other agents in a population of unknown size; moreover, the agent must know that they have all been received. Inspired by the work of the verification community on Emerson and Namjoshi’s broadcast protocols, we show that NL-power is also achieved by extending population protocols with reliable broadcasts, a simpler, standard communication primitive.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Complexity classes
  • Theory of computation → Automata over infinite objects
Keywords
  • population protocols
  • complexity theory
  • counter machines
  • distributed computing

Metrics

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

Related Versions

References

  1. Mehran Abolhasan, Tadeusz A. Wysocki, and Eryk Dutkiewicz. A review of routing protocols for mobile ad hoc networks. Ad Hoc Networks, 2(1):1-22, 2004. URL: https://doi.org/10.1016/S1570-8705(03)00043-X.
  2. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. Time-Space Trade-offs in Population Protocols. In Proc. Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2560-2579, 2017. URL: https://doi.org/10.1137/1.9781611974782.169.
  3. Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-Optimal Majority in Population Protocols. In Proc. Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2221-2239, 2018. URL: https://doi.org/10.1137/1.9781611975031.144.
  4. Dan Alistarh and Rati Gelashvili. Recent Algorithmic Advances in Population Protocols. SIGACT News, 49(3):63-73, 2018. URL: https://doi.org/10.1145/3289137.3289150.
  5. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. In Proc. 23^rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 290-299, 2004. URL: https://doi.org/10.1145/1011767.1011810.
  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, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007. URL: https://doi.org/10.1007/s00446-007-0040-2.
  8. James Aspnes. Clocked Population Protocols. In Proc. ACM Symposium on Principles of Distributed Computing (PODC), pages 431-440, 2017. Google Scholar
  9. Nathalie Bertrand, Miheer Dewaskar, Blaise Genest, and Hugo Gimbert. Controlling a Population. In Proc. 28^th International Conference on Concurrency Theory (CONCUR), volume 85, pages 12:1-12:16, 2017. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2017.12.
  10. Michael Blondin, Christoph Haase, and Filip Mazowiecki. Affine Extensions of Integer Vector Addition Systems with States. In Proc. 29^th International Conference on Concurrency Theory (CONCUR), pages 14:1-14:17, 2018. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2018.14.
  11. Dmitry Chistikov, Christoph Haase, and Simon Halfon. Context-free commutative grammars with integer counters and resets. Theoretical Computer Science, 735:147-161, 2018. URL: https://doi.org/10.1016/j.tcs.2016.06.017.
  12. Giorgio Delzanno, Jean-François Raskin, and Laurent Van Begin. Towards the Automated Verification of Multithreaded Java Programs. In Proc. 8^th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pages 173-187, 2002. URL: https://doi.org/10.1007/3-540-46002-0_13.
  13. Catherine Dufourd, Alain Finkel, and Philippe Schnoebelen. Reset Nets Between Decidability and Undecidability. In Proc. 25^th International Colloquium on Automata, Languages and Programming (ICALP), pages 103-115, 1998. URL: https://doi.org/10.1007/BFb0055044.
  14. Robert Elsässer and Tomasz Radzik. Recent Results in Population Protocols for Exact Majority and Leader Election. Bulletin of the EATCS, 126, 2018. Google Scholar
  15. E. Allen Emerson and Kedar S. Namjoshi. On Model Checking for Non-Deterministic Infinite-State Systems. In Proc. Thirteenth Annual IEEE Symposium on Logic in Computer Science (LICS), pages 70-80, 1998. URL: https://doi.org/10.1109/LICS.1998.705644.
  16. Javier Esparza, Alain Finkel, and Richard Mayr. On the Verification of Broadcast Protocols. In Proc. 14^th Annual IEEE Symposium on Logic in Computer Science (LICS), pages 352-359, 1999. URL: https://doi.org/10.1109/LICS.1999.782630.
  17. Javier Esparza, Pierre Ganty, Jérôme Leroux, and Rupak Majumdar. Verification of population protocols. Acta Informatica, 54(2):191-215, 2017. URL: https://doi.org/10.1007/s00236-016-0272-3.
  18. Alain Finkel and Jérôme Leroux. How to Compose Presburger-Accelerations: Applications to Broadcast Protocols. In Proc. 22nd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 145-156, 2002. URL: https://doi.org/10.1007/3-540-36206-1_14.
  19. Patrick C. Fischer, Albert R. Meyer, and Arnold L. Rosenberg. Counter Machines and Counter Languages. Mathematical Systems Theory, 2(3):265-283, 1968. Google Scholar
  20. Neil Immerman. Nondeterministic Space is Closed Under Complementation. SIAM Journal on Computing, 17(5):935-938, 1988. URL: https://doi.org/10.1137/0217058.
  21. David Lee and Mihalis Yannakakis. Testing Finite-State Machines: State Identification and Verification. IEEE Transactions on Computers, 43(3):306-320, 1994. URL: https://doi.org/10.1109/12.272431.
  22. Othon Michail and Paul G. Spirakis. Terminating population protocols via some minimal global knowledge assumptions. Journal of Parallel and Distributed Computing, 81-82:1-10, 2015. Google Scholar
  23. Christos H. Papadimitriou. Computational complexity. Academic Internet Publ., 2007. Google Scholar
  24. Sylvain Schmitz and Philippe Schnoebelen. The Power of Well-Structured Systems. In Proc. 24^th International Conference on Concurrency Theory (CONCUR), pages 5-24, 2013. URL: https://doi.org/10.1007/978-3-642-40184-8_2.
  25. Philippe Schnoebelen. Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets. In Proc. 35^th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 616-628, 2010. URL: https://doi.org/10.1007/978-3-642-15155-2_54.
  26. Róbert Szelepcsényi. The Method of Forced Enumeration for Nondeterministic Automata. Acta Informatica, 26(3):279-284, 1988. URL: https://doi.org/10.1007/BF00299636.
  27. Jannis Uhlendorf, Agnès Miermont, Thierry Delaveau, Gilles Charvin, François Fages, Samuel Bottani, Pascal Hersen, and Gregory Batt. In silico control of biomolecular processes. In Computational Methods in Synthetic Biology, pages 277-285. Marchisio, Mario Andrea, 2015. URL: https://doi.org/10.1007/978-1-4939-1878-2_13.
  28. Jennifer Yick, Biswanath Mukherjee, and Dipak Ghosal. Wireless sensor network survey. Computer Networks, 52(12):2292-2330, 2008. URL: https://doi.org/10.1016/j.comnet.2008.04.002.
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