The synergy of finite state machines

Yehuda Afek, Yuval Emek, Noa Kolikant

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

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.

שפה מקוריתאנגלית
כותר פרסום המארח22nd International Conference on Principles of Distributed Systems, OPODIS 2018
עורכיםJiannong Cao, Faith Ellen, Luis Rodrigues, Bernardo Ferreira
מסת"ב (אלקטרוני)9783959770989
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 ינו׳ 2019
אירוע22nd International Conference on Principles of Distributed Systems, OPODIS 2018 - Hong Kong, סין
משך הזמן: 17 דצמ׳ 201819 דצמ׳ 2018

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך125

כנס

כנס22nd International Conference on Principles of Distributed Systems, OPODIS 2018
מדינה/אזורסין
עירHong Kong
תקופה17/12/1819/12/18

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'The synergy of finite state machines'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי