Document Open Access Logo

Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols

Authors Amanda Belleville, David Doty, David Soloveichik

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.141.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Amanda Belleville
David Doty
David Soloveichik

Cite As Get BibTex

Amanda Belleville, David Doty, and David Soloveichik. Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 141:1-141:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.141

Abstract

Population protocols are a distributed computing model appropriate for describing massive numbers of agents with very limited computational power (finite automata in this paper), such as sensor networks or programmable chemical reaction networks in synthetic biology. A population protocol is said to require a leader if every valid initial configuration contains a single agent in a special "leader" state that helps to coordinate the computation. Although the class of predicates and functions computable with probability 1 (stable computation) is the same whether a leader is required or not (semilinear functions and predicates), it is not known whether a leader is necessary for fast computation. Due to the large number of agents n (synthetic molecular systems routinely have trillions of molecules), efficient population protocols are generally defined as those computing in polylogarithmic in n (parallel) time. We consider population protocols that start in leaderless initial configurations, and the computation is regarded finished when the population protocol reaches a configuration from which a different output is no longer reachable.

In this setting we show that a wide class of functions and predicates computable by population protocols are not efficiently computable (they require at least linear time), nor are some linear functions even efficiently approximable. It requires at least linear time for a population protocol even to approximate division by a constant or subtraction (or any linear function with a coefficient outside of N), in the sense that for sufficiently small gamma > 0, the output of a sublinear time protocol can stabilize outside the interval f(m) (1 +/- gamma) on infinitely many inputs m. In a complementary positive result, we show that with a sufficiently large value of gamma, a population protocol can approximate any linear f with nonnegative rational coefficients, within approximation factor gamma, in O(log n) time. We also show that it requires linear time to exactly compute a wide range of semilinear functions (e.g., f(m)=m if m is even and 2m if m is odd) and predicates (e.g., parity, equality).

Subject Classification

Keywords
  • population protocol
  • time lower bound
  • stable computation

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 molecular computation. In SODA 2017: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 2017. to appear. Google Scholar
  2. Dan Alistarh and Rati Gelashvili. Polylogarithmic-time leader election in population protocols. In ICALP 2015: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 2015. Google Scholar
  3. Dana Angluin, James Aspnes, Zoë Diamadi, Michael Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18:235-253, 2006. Preliminary version appeared in PODC 2004. URL: http://dx.doi.org/10.1007/s00446-005-0138-3.
  4. Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. In PODC 2006: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 292-299, New York, NY, USA, 2006. ACM Press. URL: http://dx.doi.org/10.1145/1146381.1146425.
  5. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183-199, September 2008. Preliminary version appeared in DISC 2006. Google Scholar
  6. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007. Google Scholar
  7. Alexandre Baccouche, Kevin Montagne, Adrien Padirac, Teruo Fujii, and Yannick Rondelez. Dynamic dna-toolbox reaction circuits: a walkthrough. Methods, 67(2):234-249, 2014. Google Scholar
  8. James M Bower and Hamid Bolouri. Computational modeling of genetic and biochemical networks. MIT press, 2004. Google Scholar
  9. E. Cardoza, Richard J. Lipton, and Albert R. Meyer. Exponential space complete problems for Petri nets and commutative semigroups (preliminary report). In STOC 1976: Proceedings of the 8th annual ACM Symposium on Theory of Computing, pages 50-54. ACM, 1976. Google Scholar
  10. Ho-Lin Chen, Rachel Cummings, David Doty, and David Soloveichik. Speed faults in computation by chemical reaction networks. Distributed Computing, 2015. to appear. Special issue of invited papers from DISC 2014. Google Scholar
  11. Ho-Lin Chen, David Doty, and David Soloveichik. Deterministic function computation with chemical reaction networks. Natural Computing, 13(4):517-534, 2014. Preliminary version appeared in DNA 2012. Google Scholar
  12. 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
  13. 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
  14. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. Distributed Computing, 2016. to appear. Special issue of invited papers from DISC 2015. Google Scholar
  15. Seymour Ginsburg and Edwin H. Spanier. Semigroups, Presburger formulas, and languages. Pacific Journal of Mathematics, 16(2):285-296, 1966. URL: http://projecteuclid.org/euclid.pjm/1102994974.
  16. Richard M Karp and Raymond E Miller. Parallel program schemata. Journal of Computer and System Sciences, 3(2):147-195, 1969. Google Scholar
  17. 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. Google Scholar
  18. Othon Michail and Paul G Spirakis. How many cooks spoil the soup? In International Colloquium on Structural Information and Communication Complexity, pages 3-18. Springer, 2016. Google Scholar
  19. Carl A Petri. Communication with automata. Technical report, DTIC Document, 1966. Google Scholar
  20. Niranjan Srinivas. Programming chemical kinetics: Engineering dynamic reaction networks with DNA strand displacement. PhD thesis, California Institute of Technology, 2015. Google Scholar
  21. Chris Thachuk, Erik Winfree, and David Soloveichik. Leakless DNA strand displacement systems. In DNA 2015: Proceedings of the 21st International Conference on DNA Computing and Molecular Programming, pages 133-153. Springer, 2015. Google Scholar
  22. Vito Volterra. Variazioni e fluttuazioni del numero d’individui in specie animali conviventi. Mem. Acad. Lincei Roma, 2:31-113, 1926. Google Scholar
  23. David Yu Zhang and Georg Seelig. Dynamic dna nanotechnology using strand-displacement reactions. Nature chemistry, 3(2):103-113, 2011. 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 About DROPS Imprint Privacy Contact