2026-07-26T08:00:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10082 2024-03-06T10:45:34Z ddc:004 open_access

The Synergy of Finite State Machines Afek, Yehuda Emek, Yuval Kolikant, Noa finite state machines stone-age model beeping communication scheme distributed network computability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yehuda Afek and Yuval Emek and Noa Kolikant 2019 Is Part Of LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2018.22 urn:nbn:de:0030-drops-100825 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.22 eng https://creativecommons.org/licenses/by/3.0/legalcode