Document Open Access Logo

On Bioelectric Algorithms

Authors Seth Gilbert, James Maguire, Calvin Newport

PDF
Thumbnail PDF

File

LIPIcs.DISC.2019.19.pdf
  • Filesize: 0.49 MB
  • 17 pages

Document Identifiers

Author Details

Seth Gilbert
  • National University of Singapore, Singapore
James Maguire
  • Georgetown University, Washington, DC, USA
Calvin Newport
  • Georgetown University, Washington, DC, USA

Funding

  • Gilbert, Seth: Supported, in part, by the MOE Tier 2 project "Beyond Worst-Case Analysis: A Tale of Distributed Algorithms" [MOE2018-T2-1-160].
  • Maguire, James: Supported in part by NSF award CCF-1649484.
  • Newport, Calvin: Supported in part by NSF awards CCF-1733842 and CCF-1649484.

Cite AsGet BibTex

Seth Gilbert, James Maguire, and Calvin Newport. On Bioelectric Algorithms. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.DISC.2019.19

Abstract

Cellular bioelectricity describes the biological phenomenon in which cells in living tissue generate and maintain patterns of voltage gradients across their membranes induced by differing concentrations of charged ions. A growing body of research suggests that bioelectric patterns represent an ancient system that plays a key role in guiding many important developmental processes including tissue regeneration, tumor suppression, and embryogenesis. This paper applies techniques from distributed algorithm theory to help better understand how cells work together to form these patterns. To do so, we present the cellular bioelectric model (CBM), a new computational model that captures the primary capabilities and constraints of bioelectric interactions between cells and their environment. We use this model to investigate several important topics from the relevant biology research literature. We begin with symmetry breaking, analyzing a simple cell definition that when combined in single hop or multihop topologies, efficiently solves leader election and the maximal independent set problem, respectively - indicating that these classical symmetry breaking tasks are well-matched to bioelectric mechanisms. We then turn our attention to the information processing ability of bioelectric cells, exploring upper and lower bounds for approximate solutions to threshold and majority detection, and then proving that these systems are in fact Turing complete - resolving an open question about the computational power of bioelectric interactions.

Subject Classification

ACM Subject Classification
  • Applied computing → Biological networks
  • Theory of computation → Distributed algorithms
Keywords
  • biological distributed algorithms
  • bioelectric networks
  • natural algorithms

Metrics

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

Related Versions

References

  1. Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, and Fabian Kuhn. Beeping a Maximal Independent Set. In Proceedings of the Symposium on Distributed Computing (DISC), 2011. Google Scholar
  2. Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, and Fabian Kuhn. Beeping a maximal independent set. Distributed Computing, 26(4):195-208, 2013. Google Scholar
  3. Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, and Fabian Kuhn. Beeping a maximal independent set. Distributed Computing, 26(4):195-208, 2013. Google Scholar
  4. Yehuda Afek, Noga Alon, Omer Barad, Eran Hornstein, Naama Barkai, and Ziv Bar-Joseph. A biological solution to a fundamental distributed computing problem. Science, 331(6014):183-185, 2011. Google Scholar
  5. 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
  6. Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. In Proceedings of the Symposium on Principles of Distributed Computing (PODC), pages 292-299, 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. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183-199, 2008. Google Scholar
  9. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007. Google Scholar
  10. Ioannis Chatzigiannakis and Paul G. Spirakis. The Dynamics of Probabilistic Population Protocols. In Proceedings of the Symposium on Distributed Computing (DISC), 2008. Google Scholar
  11. Ho-Lin Chen, Rachel Cummings, David Doty, and David Soloveichik. Speed faults in computation by chemical reaction networks. Distributed Computing, 30(5):373-390, 2017. Google Scholar
  12. Ho-Lin Chen, David Doty, and David Soloveichik. Deterministic function computation with chemical reaction networks. Natural computing, 13(4):517-534, 2014. Google Scholar
  13. Alejandro Cornejo, Anna Dornhaus, Nancy Lynch, and Radhika Nagpal. Task allocation in ant colonies. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 46-60. Springer, 2014. Google Scholar
  14. Alejandro Cornejo and Fabian Kuhn. Deploying Wireless Networks with Beeps. In Proceedings of the Symposium on Distributed Computing (DISC), 2010. Google Scholar
  15. Julius Degesys and Radhika Nagpal. Towards desynchronization of multi-hop topologies. In Proceedings of the International Conference on Self-Adaptive and Self-Organizing Systems, 2008 (SASO), 2008. Google Scholar
  16. Julius Degesys, Ian Rose, Ankit Patel, and Radhika Nagpal. DESYNC: self-organizing desynchronization and TDMA on wireless sensor networks. In Proceedings of the International Conference on Information Processing in Sensor Networks, 2007. Google Scholar
  17. Fallon Durant, Junji Morokuma, Christopher Fields, Katherine Williams, Dany Spencer Adams, and Michael Levin. Long-term, stochastic editing of regenerative anatomy via targeting endogenous bioelectric gradients. Biophysical journal, 112(10):2231-2243, 2017. Google Scholar
  18. Yuval Emek and Roger Wattenhofer. Stone Age Distributed Computing. In Proceedings of the Symposium on Principles of Distributed Computing (PODC), 2013. Google Scholar
  19. Ofer Feinerman, Amos Korman, Zvi Lotker, and Jean-Sébastien Sereni. Collaborative search on the plane without communication. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 77-86. ACM, 2012. Google Scholar
  20. Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva, and Nancy Lynch. Distributed house-hunting in ant colonies. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 57-66. ACM, 2015. Google Scholar
  21. Seth Gilbert and Calvin Newport. The computational power of beeps. In International Symposium on Distributed Computing, pages 31-46. Springer, 2015. Google Scholar
  22. Jessica Hamzelou. Bioelectric tweak makes flatworms grow a head instead of a tail. New Scientist, May 2017. Google Scholar
  23. Fabian Kuhn, Thomas Moscibroda, and Rogert Wattenhofer. On the locality of bounded growth. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 60-68. ACM, 2005. Google Scholar
  24. Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva. Trade-offs between selection complexity and performance when searching the plane without communication. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 252-261. ACM, 2014. Google Scholar
  25. Michael Levin and Christopher J Martyniuk. The bioelectric code: An ancient computational medium for dynamic control of growth and form. Biosystems, 164:76-93, 2017. Google Scholar
  26. Nancy Lynch, Cameron Musco, and Merav Parter. Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks. In Proceedings of the Conference on Innovations in Theoretical Computer Science (ITCS 2017), pages 15:1-15:44, 2017. Google Scholar
  27. Wolfgang Maass. Networks of spiking neurons: the third generation of neural network models. Neural networks, 10(9):1659-1671, 1997. Google Scholar
  28. Arik Motskin, Tim Roughgarden, Primoz Skraba, and Leonidas J. Guibas. Lightweight Coloring and Desynchronization for Networks. In Proceedings of the of the Conference on Computer Communication (INFOCOM), 2009. Google Scholar
  29. Saket Navlakha and Ziv Bar-Joseph. Algorithms in nature: the convergence of systems biology and computational thinking. Molecular Systems Biology, 7(1):546, 2011. Google Scholar
  30. Saket Navlakha and Ziv Bar-Joseph. Distributed information processing in biological and computational systems. Communications of the ACM, 58(1):94-102, 2014. Google Scholar
  31. Calvin Newport. Radio network lower bounds made easy. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 258-272. Springer, 2014. Google Scholar
  32. Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958. Google Scholar
  33. Alex Scott, Peter Jeavons, and Lei Xu. Feedback from nature: an optimal distributed algorithm for maximal independent set selection. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 147-156. ACM, 2013. Google Scholar
  34. Alex Scott, Peter Jeavons, and Lei Xu. Feedback from nature: an optimal distributed algorithm for maximal independent set selection. In Proceedings of the Symposium on Principles of Distributed Computing (PODC), 2013. Google Scholar
  35. Asaf Shiloni, Noa Agmon, and Gal A Kaminka. Of robot ants and elephants: A computational comparison. Theoretical Computer Science, 412(41):5771-5788, 2011. Google Scholar
  36. Hava T Siegelmann and Eduardo D Sontag. Turing computability with neural nets. Applied Mathematics Letters, 4(6):77-80, 1991. Google Scholar
  37. David Soloveichik, Matthew Cook, Erik Winfree, and Jehoshua Bruck. Computation with finite stochastic chemical reaction networks. natural computing, 7(4):615-633, 2008. 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