Document Open Access Logo

Distributed Computation with Continual Population Growth

Authors Da-Jung Cho , Matthias Függer , Corbin Hopper , Manish Kushwaha , Thomas Nowak , Quentin Soubeyran

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.7.pdf
  • Filesize: 1.02 MB
  • 17 pages

Document Identifiers

Author Details

Da-Jung Cho
  • University of Kassel, Germany
Matthias Függer
  • CNRS, LSV, ENS Paris-Saclay, Université Paris-Saclay, Inria, Gif-sur-Yvette, France
Corbin Hopper
  • ENS Paris-Saclay, Gif-sur-Yvette, France
  • Université Paris-Saclay, CNRS, Orsay, France
Manish Kushwaha
  • Université Paris-Saclay, INRAE, AgroParisTech, Micalis Institute, Jouy-en-Josas, France
Thomas Nowak
  • Université Paris-Saclay, CNRS, Orsay, France
Quentin Soubeyran
  • École polytechnique, Institut Polytechnique de Paris, Route de Saclay, Palaiseau, France
  • Université Paris-Saclay, CNRS, Orsay, France

Acknowledgements

We acknowledge support from the Digicosme working group HicDiesMeus, Ile-de-France region’s DIM-RFSI, INRAE’s MICA department, and the CNRS project ABIDE. We thank Joel Rybicki for feedback on an earlier version.

Cite AsGet BibTex

Da-Jung Cho, Matthias Függer, Corbin Hopper, Manish Kushwaha, Thomas Nowak, and Quentin Soubeyran. Distributed Computation with Continual Population Growth. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.7

Abstract

Computing with synthetically engineered bacteria is a vibrant and active field with numerous applications in bio-production, bio-sensing, and medicine. Motivated by the lack of robustness and by resource limitation inside single cells, distributed approaches with communication among bacteria have recently gained in interest. In this paper, we focus on the problem of population growth happening concurrently, and possibly interfering, with the desired bio-computation. Specifically, we present a fast protocol in systems with continuous population growth for the majority consensus problem and prove that it correctly identifies the initial majority among two inputs with high probability if the initial difference is Ω(√{nlog n}) where n is the total initial population. We also present a fast protocol that correctly computes the NAND of two inputs with high probability. We demonstrate that combining the NAND gate protocol with the continuous-growth majority consensus protocol, using the latter as an amplifier, it is possible to implement circuits computing arbitrary Boolean functions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • microbiological circuits
  • majority consensus
  • birth-death processes

Metrics

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

Related Versions

References

  1. J. Christopher Anderson, Elizabeth J. Clarke, Adam P. Arkin, and Christopher A. Voigt. Environmentally controlled invasion of cancer cells by engineered bacteria. Journal of Molecular Biology, 355(4):619-627, January 2006. URL: https://doi.org/10.1016/j.jmb.2005.10.076.
  2. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183-199, 2008. Google Scholar
  3. Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2):87-102, March 2008. URL: https://doi.org/10.1007/s00446-008-0059-z.
  4. L Billard. Competition between two species. Stochastic Processes and their Applications, 2(4):391-398, 1974. Google Scholar
  5. Pierre Brémaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, Heidelberg, 1999. Google Scholar
  6. Anne Condon, Monir Hajiaghayi, David Kirkpatrick, and Ján Maňuch. Approximate majority analyses using tri-molecular chemical reaction networks. Natural Computing, 19:249-270, 2020. Google Scholar
  7. Rachel Cummings, David Doty, and David Soloveichik. Probability 1 computation with chemical reaction networks. Natural Computing, 15:245-261, 2016. Google Scholar
  8. Ramiz Daniel, Jacob R. Rubens, Rahul Sarpeshkar, and Timothy K. Lu. Synthetic analog computation in living cells. Nature, 497(7451):619-623, May 2013. URL: https://doi.org/10.1038/nature12148.
  9. Tatiana Dimitriu, Chantal Lotton, Julien Bénard-Capelle, Dusan Misevic, Sam P Brown, Ariel B Lindner, and François Taddei. Genetic information transfer promotes cooperation in bacteria. Proceedings of the National Academy of Sciences, 111(30):11103-11108, 2014. Google Scholar
  10. William Feller. Die Grundlagen der volterraschen Theorie des Kampfes ums Dasein in wahrscheinlichkeitstheoretischer Behandlung (1939). In Selected Papers I, pages 441-470. Springer, 2015. Google Scholar
  11. Matthias Függer, Manish Kushwaha, and Thomas Nowak. Digital circuit design for biological and silicon computers. In Advances in Synthetic Biology, pages 153-171. Springer, 2020. Google Scholar
  12. Daniel T Gillespie. Approximate accelerated stochastic simulation of chemically reacting systems. The Journal of Chemical Physics, 115(4):1716-1733, 2001. Google Scholar
  13. Antonio Gómez-Corral and M López García. Extinction times and size of the surviving species in a two-species competition process. Journal of Mathematical Biology, 64(1-2):255-289, 2012. Google Scholar
  14. S. Hoops, S. Sahle, R. Gauges, C. Lee, J. Pahle, N. Simus, M. Singhal, L. Xu, P. Mendes, and U. Kummer. COPASI-a COmplex PAthway SImulator. Bioinformatics, 22(24):3067-3074, October 2006. URL: https://doi.org/10.1093/bioinformatics/btl485.
  15. Samuel Karlin and Howard M. Taylor. A First Course in Stochastic Processes. Academic Press, New York, 2 edition, 1975. Google Scholar
  16. David G Kendall. Branching processes since 1873. Journal of the London Mathematical Society, 1(1):385-406, 1966. Google Scholar
  17. Eric Libby and William C Ratcliff. Ratcheting the evolution of multicellularity. Science, 346(6208):426-427, 2014. Google Scholar
  18. Nancy A Lynch. Distributed algorithms. Morgan Kaufmann, 1996. Google Scholar
  19. John P Marken and Richard M Murray. Addressable," packet-based" intercellular communication through plasmid conjugation. bioRxiv, page 591552, 2019. Google Scholar
  20. Tae Seok Moon, Chunbo Lou, Alvin Tamsir, Brynne C. Stanton, and Christopher A. Voigt. Genetic programs constructed from layered logic gates in single cells. Nature, 491(7423):249-253, October 2012. URL: https://doi.org/10.1038/nature11516.
  21. Chris J Myers. Asynchronous Circuit Design. John Wiley & Sons, 2001. Google Scholar
  22. Artem S Novozhilov, Georgy P Karev, and Eugene V Koonin. Biological applications of the theory of birth-and-death processes. Briefings in Bioinformatics, 7(1):70-85, 2006. Google Scholar
  23. Monica E Ortiz and Drew Endy. Engineered cell-cell communication via DNA messaging. Journal of Biological Engineering, 6(1):16, December 2012. URL: https://doi.org/10.1186/1754-1611-6-16.
  24. C. J. Paddon, P. J. Westfall, D. J. Pitera, K. Benjamin, K. Fisher, D. McPhee, M. D. Leavell, A. Tai, A. Main, D. Eng, D. R. Polichuk, K. H. Teoh, D. W. Reed, T. Treynor, J. Lenihan, H. Jiang, M. Fleck, S. Bajad, G. Dang, D. Dengrove, D. Diola, G. Dorin, K. W. Ellens, S. Fickes, J. Galazzo, S. P. Gaucher, T. Geistlinger, R. Henry, M. Hepp, T. Horning, T. Iqbal, L. Kizer, B. Lieu, D. Melis, N. Moss, R. Regentin, S. Secrest, H. Tsuruta, R. Vazquez, L. F. Westblade, L. Xu, M. Yu, Y. Zhang, L. Zhao, J. Lievense, P. S. Covello, J. D. Keasling, K. K. Reiling, N. S. Renninger, and J. D. Newman. High-level semi-synthetic production of the potent antimalarial artemisinin. Nature, 496(7446):528-532, April 2013. URL: https://doi.org/10.1038/nature12051.
  25. Amir Pandi, Mathilde Koch, Peter L Voyvodic, Paul Soudier, Jérôme Bonnet, Manish Kushwaha, and Jean-Loup Faulon. Metabolic perceptrons for neural computing in biological systems. Nature Communications, 10(1):1-13, 2019. Google Scholar
  26. William C Ratcliff, R Ford Denison, Mark Borrello, and Michael Travisano. Experimental evolution of multicellularity. Proceedings of the National Academy of Sciences, 109(5):1595-1600, 2012. Google Scholar
  27. Sergi Regot, Javier Macia, Núria Conde, Kentaro Furukawa, Jimmy Kjellén, Tom Peeters, Stefan Hohmann, Eulàlia de Nadal, Francesc Posas, and Ricard Solé. Distributed biological computation with multicellular engineered networks. Nature, 469(7329):207-211, December 2010. URL: https://doi.org/10.1038/nature09679.
  28. GEH Reuter. Competition processes. In Proc. 4th Berkeley Symp. Math. Statist. Prob, volume 2, pages 421-430, 1961. Google Scholar
  29. CJ Ridler-Rowe. On competition between two species. Journal of Applied Probability, 15(3):457-465, 1978. Google Scholar
  30. Thomas L Saaty. Elements of Queueing Theory, volume 34203. McGraw-Hill New York, 1961. Google Scholar
  31. Sebastian R Schmidl, Felix Ekness, Katri Sofjan, Kristina N-M Daeffler, Kathryn R Brink, Brian P Landry, Karl P Gerhardt, Nikola Dyulgyarov, Ravi U Sheth, and Jeffrey J Tabor. Rewiring bacterial two-component systems by modular dna-binding domain swapping. Nature Chemical Biology, 15(7):690-698, 2019. Google Scholar
  32. Shimyn Slomovic, Keith Pardee, and James J Collins. Synthetic biology devices for in vitro and in vivo diagnostics. Proceedings of the National Academy of Sciences, 112(47):14429-14435, 2015. Google Scholar
  33. David Soloveichik, Matthew Cook, Erik Winfree, and Jehoshua Bruck. Computation with finite stochastic chemical reaction networks. Natural Computing, 7(4):615-633, February 2008. URL: https://doi.org/10.1007/s11047-008-9067-y.
  34. Jens Sparsø and Steve Furber. Principles of asynchronous circuit design. Springer, 2002. Google Scholar
  35. Jeffrey J Tabor, Howard M Salis, Zachary Booth Simpson, Aaron A Chevalier, Anselm Levskaya, Edward M Marcotte, Christopher A Voigt, and Andrew D Ellington. A synthetic genetic edge detection program. Cell, 137(7):1272-1281, 2009. Google Scholar
  36. Alvin Tamsir, Jeffrey J. Tabor, and Christopher A. Voigt. Robust multicellular computing using genetically encoded NOR gates and chemical `wires'. Nature, 469(7329):212-215, December 2010. URL: https://doi.org/10.1038/nature09565.
  37. Pei Kun R Tay, Peter Q Nguyen, and Neel S Joshi. A synthetic circuit for mercury bioremediation using self-assembling functional amyloids. ACS Synthetic Biology, 6(10):1841-1850, 2017. Google Scholar
  38. Vito Volterra. Leçons sur la Theorie Mathematique de la Lutte pour la Vie. Gauthier-Villars, Paris, 1931. 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