Document Open Access Logo

Approximate Majority with Catalytic Inputs

Authors Talley Amir, James Aspnes, John Lazarsfeld

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.19.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Author Details

Talley Amir
  • Yale University, New Haven, CT, USA
James Aspnes
  • Yale University, New Haven, CT, USA
John Lazarsfeld
  • Yale University, New Haven, CT, USA

Funding

  • Aspnes, James: Supported in part by NSF grant CCF-1650596.

Acknowledgements

The authors would like to thank Anne Condon, Monir Hajiaghayi, David Kirkpatrick, and J{á}n Maňuch for a helpful discussion regarding the analysis of the DBAM protocol. The authors are also grateful for a discussion with Francesco d’Amore, Andrea Clementi, and Emanuele Natale, who pointed out the connection between catalytic agents in population protocols and stubborn agents in other types of multi-agent systems. We also thank the anonymous reviewers for their helpful feedback.

Cite AsGet BibTex

Talley Amir, James Aspnes, and John Lazarsfeld. Approximate Majority with Catalytic Inputs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.OPODIS.2020.19

Abstract

Population protocols [Dana Angluin et al., 2006] are a class of algorithms for modeling distributed computation in networks of finite-state agents communicating through pairwise interactions. Their suitability for analyzing numerous chemical processes has motivated the adaptation of the original population protocol framework to better model these chemical systems. In this paper, we further the study of two such adaptations in the context of solving approximate majority: persistent-state agents (or catalysts) and spontaneous state changes (or leaks). Based on models considered in recent protocols for populations with persistent-state agents [Bartlomiej Dudek and Adrian Kosowski, 2018; Alistarh et al., 2017; Dan Alistarh et al., 2020], we assume a population with n catalytic input agents and m worker agents, and the goal of the worker agents is to compute some predicate over the states of the catalytic inputs. We call this model the Catalytic Input (CI) model. For m = Θ(n), we show that computing the parity of the input population with high probability requires at least Ω(n²) total interactions, demonstrating a strong separation between the CI model and the standard population protocol model. On the other hand, we show that the simple third-state dynamics [Angluin et al., 2008; Perron et al., 2009] for approximate majority in the standard model can be naturally adapted to the CI model: we present such a constant-state protocol for the CI model that solves approximate majority in O(n log n) total steps with high probability when the input margin is Ω(√{n log n}). We then show the robustness of third-state dynamics protocols to the transient leaks events introduced by [Alistarh et al., 2017; Dan Alistarh et al., 2020]. In both the original and CI models, these protocols successfully compute approximate majority with high probability in the presence of leaks occurring at each step with probability β ≤ O(√{n log n}/n). The resilience of these dynamics to leaks exhibits similarities to previous work involving Byzantine agents, and we define and prove a notion of equivalence between the two.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Distributed algorithms
Keywords
  • population protocols
  • approximate majority
  • catalysts
  • leaks
  • lower bound

Metrics

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

Related Versions

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: https://doi.org/10.1137/1.9781611974782.169.
  2. Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2221-2239. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.144.
  3. Dan Alistarh, Bartłomiej Dudek, Adrian Kosowski, David Soloveichik, and Przemysław Uznański. Robust detection in leak-prone population protocols. In International Conference on DNA-Based Computers, pages 155-171. Springer, 2017. Google Scholar
  4. Dan Alistarh and Rati Gelashvili. Polylogarithmic-time leader election in population protocols. In Proceedings, Part II, of the 42Nd International Colloquium on Automata, Languages, and Programming - Volume 9135, ICALP 2015, pages 479-491, Berlin, Heidelberg, 2015. Springer-Verlag. URL: https://doi.org/10.1007/978-3-662-47666-6_38.
  5. Dan Alistarh, Martin Töpfer, and Przemysław Uznański. Robust comparison in population protocols, 2020. URL: http://arxiv.org/abs/2003.06485.
  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. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2):87-102, 2008. Google Scholar
  8. Luca Becchetti, Andrea Clementi, and Emanuele Natale. Consensus dynamics: An overview. ACM SIGACT News, 51(1):58-104, 2020. Google Scholar
  9. Luca Cardelli and Attila Csikász-Nagy. The cell cycle switch computes approximate majority. Scientific reports, 2:656, September 2012. URL: https://doi.org/10.1038/srep00656.
  10. Ho-Lin Chen, David Doty, and David Soloveichik. Deterministic function computation with chemical reaction networks. Nat. Comput., 13(4):517-534, 2014. URL: https://doi.org/10.1007/s11047-013-9393-6.
  11. 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, September 2013. URL: https://doi.org/10.1038/nnano.2013.189.
  12. Anne Condon, Monir Hajiaghayi, David Kirkpatrick, and Ján Maňuch. Approximate majority analyses using tri-molecular chemical reaction networks. Natural Computing, pages 1-22, 2019. Google Scholar
  13. Francesco d'Amore, Andrea E. F. Clementi, and Emanuele Natale. Phase transition of a non-linear opinion dynamics with noisy interactions - (extended abstract). In Andrea Werneck Richa and Christian Scheideler, editors, Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29 - July 1, 2020, Proceedings, volume 12156 of Lecture Notes in Computer Science, pages 255-272. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-54921-3_15.
  14. Bartlomiej Dudek and Adrian Kosowski. Universal protocols for information dissemination using emergent signals. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 87-99. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188818.
  15. William Feller. An introduction to probability theory and its applications. Vol. I. Third edition. John Wiley & Sons Inc., New York, 1968. Google Scholar
  16. Leszek Gasieniec and Grzegorz Stachowiak. Fast space optimal leader election in population protocols. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2653-2667. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.169.
  17. Leszek Gąsieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. 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, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3323165.3323178.
  18. Geoffrey R Grimmett and David R Stirzaker. Probability and Random Processes. Oxford University Press, 2001. Google Scholar
  19. Adrian Kosowski and Przemysław Uznański. Population protocols are fast. arXiv preprint arXiv:1802.06872, 2018. Google Scholar
  20. Etienne Perron, Dinkar Vasudevan, and Milan Vojnovic. Using three states for binary consensus on complete graphs. In IEEE INFOCOM 2009, pages 2527-2535. IEEE, 2009. Google Scholar
  21. Chris Thachuk, Erik Winfree, and David Soloveichik. Leakless DNA strand displacement systems. In Andrew Phillips and Peng Yin, editors, DNA Computing and Molecular Programming - 21st International Conference, DNA 21, Boston and Cambridge, MA, USA, August 17-21, 2015. Proceedings, volume 9211 of Lecture Notes in Computer Science, pages 133-153. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21999-8_9.
  22. Boya Wang, Chris Thachuk, Andrew D. Ellington, Erik Winfree, and David Soloveichik. Effective design principles for leakless strand displacement systems. Proceedings of the National Academy of Sciences, 115(52):E12182-E12191, 2018. URL: https://doi.org/10.1073/pnas.1806859115.
  23. A. C. Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222-227, 1977. Google Scholar
  24. Ercan Yildiz, Asuman Ozdaglar, Daron Acemoglu, Amin Saberi, and Anna Scaglione. Binary opinion dynamics with stubborn agents. ACM Transactions on Economics and Computation (TEAC), 1(4):1-30, 2013. 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