Document Open Access Logo

The Synergy of Finite State Machines

Authors Yehuda Afek, Yuval Emek, Noa Kolikant

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.22.pdf
  • Filesize: 461 kB
  • 16 pages

Document Identifiers

Author Details

Yehuda Afek
  • Tel Aviv University, Tel Aviv, Israel
Yuval Emek
  • Technion - Israel Institute of Technology, Haifa, Israel
Noa Kolikant
  • Tel Aviv University, Tel Aviv, Israel

Funding

  • Afek, Yehuda: The work of Y. Afek was partially supported by a grant from the Blavatnik Cyber Security Council and the Blavatnik Computer Science Research Fund.
  • Emek, Yuval: The work of Y. Emek was supported in part by an Israeli Science Foundation grant number 1016/17.

Cite AsGet BibTex

Yehuda Afek, Yuval Emek, and Noa Kolikant. The Synergy of Finite State Machines. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.OPODIS.2018.22

Abstract

What can be computed by a network of n randomized finite state machines communicating under the stone age model (Emek & Wattenhofer, PODC 2013)? The inherent linear upper bound on the total space of the network implies that its global computational power is not larger than that of a randomized linear space Turing machine, but is this tight? We answer this question affirmatively for bounded degree networks by introducing a stone age algorithm (operating under the most restrictive form of the model) that given a designated I/O node, constructs a tour in the network that enables the simulation of the Turing machine's tape. To construct the tour with high probability, we first show how to 2-hop color the network concurrently with building a spanning tree.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • finite state machines
  • stone-age model
  • beeping communication scheme
  • distributed network computability

Metrics

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

Related Versions

References

  1. Y. Afek, N. Alon, O. Barad, E. Hornstein, N. Barkai, and Z. Bar-Joseph. A biological solution to a fundamental distributed computing problem. Science, 331(6014):183-185, 2011. Google Scholar
  2. Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, and Fabian Kuhn. Beeping a Maximal Independent Set. In DISC, pages 32-50, 2011. Google Scholar
  3. Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, and Fabian Kuhn. Beeping a Maximal Independent Set. CoRR, abs/1206.0150, 2012. URL: http://arxiv.org/abs/1206.0150,
  4. Yehuda Afek, Baruch Awerbuch, and Eli Gafni. Applying Static Network Protocols to Dynamic Networks. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, SFCS '87, pages 358-370, Washington, DC, USA, 1987. IEEE Computer Society. URL: http://dx.doi.org/10.1109/SFCS.1987.7.
  5. Yehuda Afek, Yuval Emek, and Noa Kolikant. Selecting a Leader in a Network of Finite State Machines. In DISC, 2018. The full version can be obtained from URL: http://arxiv.org/abs/1805.05660.
  6. Yehuda Afek, Yuval Emek, and Noa Kolikant. The Synergy of Finite State Machines (Full Version). http://yemek.net.technion.ac.il/files/tsfsm.pdf, 2018.
  7. D. Angluin, J. Aspnes, Z. Diamadi, M.J. Fischer, and R. Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, pages 235-253, 2006. Google Scholar
  8. J. Aspnes and E. Ruppert. An introduction to population protocols. In Benoît Garbinato, Hugo Miranda, and Luís Rodrigues, editors, Middleware for Network Eccentric and Mobile Applications, pages 97-120. Springer-Verlag, 2009. Google Scholar
  9. Baruch Awerbuch. Complexity of Network Synchronization. J. ACM, 32(4):804-823, 1985. Google Scholar
  10. Y. Benenson, T. Paz-Elizur, R. Adar, E. Keinan, Z. Livneh, and E. Shapiro. Programmable and autonomous computing machine made of biomolecules. Nature, 414(6862):430-434, 2001. Google Scholar
  11. S. Cannon, J.J. Daymude, D. Randall, and A.W. Richa. A Markov chain algorithm for compression in self-organizing particle systems. In PODC, pages 279-288, 2016. Google Scholar
  12. Lihi Cohen, Yuval Emek, Oren Louidor, and Jara Uitto. Exploring an Infinite Space with Finite Memory Scouts. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 207-224, 2017. Google Scholar
  13. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. Google Scholar
  14. Alejandro Cornejo and Fabian Kuhn. Deploying Wireless Networks with Beeps. In DISC, pages 148-162, 2010. Google Scholar
  15. Z. Derakhshandeh, R. Gmyr, A. Porter, A.W. Richa, C. Scheideler, and T. Strothmann. On the runtime of universal coating for programmable matter. In DNA, pages 148-164, 2016. Google Scholar
  16. Z. Derakhshandeh, R. Gmyr, A.W. Richa, C. Scheideler, and T. Strothmann. An algorithmic framework for shape formation problems in self-organizing particle systems. In NANOCOM, pages 21:1-21:2, 2015. Google Scholar
  17. Z. Derakhshandeh, R. Gmyr, A.W. Richa, C. Scheideler, and T. Strothmann. Universal shape formation for programmable matter. In SPAA, pages 289-299, 2016. Google Scholar
  18. Z. Derakhshandeh, R. Gmyr, A.W. Richa, C. Scheideler, T. Strothmann, and S. Tzur-David. Infinite object coating in the amoebot model. CoRR, abs/1411.2356, 2014. Google Scholar
  19. Z. Derakhshandeh, R. Gmyr, T. Strothmann, R.A. Bazzi, A.W. Richa, and C. Scheideler. Leader election and shape formation with self-organizing programmable matter. In DNA, pages 117-132, 2015. Google Scholar
  20. S. Dolev, R. Gmyr, A.W. Richa, and C. Scheideler. Ameba-inspired self-organizing particle systems. CoRR, abs/1307.4259, 2013. Google Scholar
  21. D. Doty. Timing in chemical reaction networks. In SODA, pages 772-784, 2014. Google Scholar
  22. Y. Emek, T. Langner, D. Stolz, J. Uitto, and R. Wattenhofer. How many ants does it take to find the food? Theor. Comput. Sci., 608:255-267, 2015. Google Scholar
  23. Y. Emek, T. Langner, J. Uitto, and R. Wattenhofer. Solving the ANTS problem with asynchronous finite state machines. In ICALP, pages 471-482, 2014. Google Scholar
  24. Y. Emek and J. Uitto. Dynamic Networks of Finite State Machines. In SIROCCO, pages 19-34, 2016. Google Scholar
  25. Y. Emek and R. Wattenhofer. Stone age distributed computing. In PODC, pages 137-146, 2013. The full version can be obtained from URL: http://yemek.net.technion.ac.il/files/stone-age.pdf.
  26. Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, and Roger Wattenhofer. How Many Ants Does It Take To Find the Food? In 21th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Hida Takayama, Japan, July 2014. Google Scholar
  27. Yuval Emek, Christoph Pfister, Jochen Seidel, and Roger Wattenhofer. Anonymous networks: randomization = 2-hop coloring. In ACM Symposium on Principles of Distributed Computing, PODC, pages 96-105, 2014. Google Scholar
  28. O. Feinerman and A. Korman. Memory lower bounds for randomized collaborative search and implications for biology. In DISC, pages 61-75, 2012. Google Scholar
  29. O. Feinerman and A. Korman. Theoretical distributed computing meets biology: a review, pages 1-18. Springer Berlin Heidelberg, 2013. Google Scholar
  30. O. Feinerman, A. Korman, Z. Lotker, and J.S. Sereni. Collaborative search on the plane without communication. In PODC, pages 77-86, 2012. Google Scholar
  31. M. Gardner. The fantastic combinations of John Conway’s new solitaire game `life'. Scientific American, 223(4):120-123, 1970. Google Scholar
  32. Alon Itai and Michael Rodeh. Symmetry breaking in distributed networks. Inf. Comput., 88(1):60-87, 1990. Google Scholar
  33. T. Langner, B. Keller, J. Uitto, and R. Wattenhofer. Overcoming obstacles with ants. In OPODIS, pages 9:1-9:17, 2015. Google Scholar
  34. T. Langner, J. Uitto, D. Stolz, and R. Wattenhofer. Fault-tolerant ANTS. In DISC, pages 31-45, 2014. Google Scholar
  35. O. Michail, I. Chatzigiannakis, and P.G. Spirakis. New models for population protocols. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2011. Google Scholar
  36. S. Navlakha and Z. Bar-Joseph. Distributed information processing in biological and computational systems. Commun. ACM, 58(1):94-102, 2014. Google Scholar
  37. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  38. NSF workshop on self-organizing particle systems (SOPS). http://sops2014.cs.upb.de/, 2014.
  39. J. von Neumann. Theory of self-reproducing automata. University of Illinois Press, Champaign, IL, USA, 1966. Google Scholar
  40. S. Wolfram. A new kind of science. Wolfram Media, Champaign, Illinois, 2002. 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