文章基本信息

标题：The Synergy of Finite State Machines
本地全文：下载
作者：Yehuda Afek ; Yuval Emek ; Noa Kolikant 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：125
页码：1-16
DOI：10.4230/LIPIcs.OPODIS.2018.22
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：finite state machines; stone-age model; beeping communication scheme; distributed network computability