LIPIcs.DISC.2017.42.pdf
- Filesize: 302 kB
- 3 pages
Document
Brief Announcement: The Synergy of Finite State Machines
Authors
-
Part of:
Volume:
31st International Symposium on Distributed Computing (DISC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-10-12
Cite As Get BibTex
Yehuda Afek, Yuval Emek, and Noa Kolikant. Brief Announcement: The Synergy of Finite State Machines. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.DISC.2017.42
Abstract
What can be computed by a network of n randomized finite state machines communicating under the stone age model (a generalization of the beeping model’s communication scheme)? 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? The reported reseach answers 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, it is first shown how to 2-hop color the network concurrently with building a spanning tree with high probability.
Subject Classification
Keywords
- beeping communication
- finite state machine
- stone age model
- distributed network complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
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.
-
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.
-
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.
- Y. Emek and R. Wattenhofer. Stone age distributed computing. In PODC, pages 137-146, 2013. The full version can be obtained from URL: https://ie.technion.ac.il/~yemek/Publications/stone-age.pdf.
-
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.
-
O. Feinerman and A. Korman. Theoretical distributed computing meets biology: a review, pages 1-18. Springer Berlin Heidelberg, 2013.
-
O. Michail, I. Chatzigiannakis, and P.G. Spirakis. New models for population protocols. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2011.
-
S. Navlakha and Z. Bar-Joseph. Distributed information processing in biological and computational systems. Commun. ACM, 58(1):94-102, 2014.