License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.42
URN: urn:nbn:de:0030-drops-80072
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8007/
Go to the corresponding LIPIcs Volume Portal

Afek, Yehuda ; Emek, Yuval ; Kolikant, Noa

Brief Announcement: The Synergy of Finite State Machines

pdf-format:
LIPIcs-DISC-2017-42.pdf (0.3 MB)

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.

BibTeX - Entry

@InProceedings{afek_et_al:LIPIcs:2017:8007,
  author =	{Yehuda Afek and Yuval Emek and Noa Kolikant},
  title =	{{Brief Announcement: The Synergy of Finite State Machines}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{42:1--42:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8007},
  URN =		{urn:nbn:de:0030-drops-80072},
  doi =		{10.4230/LIPIcs.DISC.2017.42},
  annote =	{Keywords: beeping communication, finite state machine, stone age model, distributed network complexity}
}

Keywords: beeping communication, finite state machine, stone age model, distributed network complexity
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI