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.OPODIS.2019.25
URN: urn:nbn:de:0030-drops-118114
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11811/
Flocchini, Paola ;
Santoro, Nicola ;
Wada, Koichi
On Memory, Communication, and Synchronous Schedulers When Moving and Computing
Abstract
We investigate the computational power of distributed systems whose autonomous computational entities, called robots, move and operate in the 2-dimensional Euclidean plane in synchronous Look-Compute-Move (LCM) cycles. Specifically, we focus on the power of persistent memory and that of explicit communication, and on their computational relationship.
In the most common model, OBLOT, the robots are oblivious (no persistent memory) and silent (no explicit means of communication). In contrast, in the LUMI model, each robot is equipped with a constant-sized persistent memory (called light), visible to all the robots; hence, these luminous robots are capable in each cycle of both remembering and communicating. Since luminous robots are computationally more powerful than the standard oblivious one, immediate important questions are about the individual computational power of persistent memory and of explicit communication. In particular, which of the two capabilities, memory or communication, is more important? in other words, is it better to remember or to communicate ?
In this paper we address these questions, focusing on two sub-models of LUMI: FSTA, where the robots have a constant-size persistent memory but are silent; and FCOM, where the robots can communicate a constant number of bits but are oblivious. We analyze the relationship among all these models and provide a complete exhaustive map of their computational relationship. Among other things, we prove that communication is more powerful than persistent memory under the fully synchronous scheduler Fsynch, while they are incomparable under the semi-synchronous scheduler Ssynch.
BibTeX - Entry
@InProceedings{flocchini_et_al:LIPIcs:2020:11811,
author = {Paola Flocchini and Nicola Santoro and Koichi Wada},
title = {{On Memory, Communication, and Synchronous Schedulers When Moving and Computing}},
booktitle = {23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
pages = {25:1--25:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-133-7},
ISSN = {1868-8969},
year = {2020},
volume = {153},
editor = {Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11811},
URN = {urn:nbn:de:0030-drops-118114},
doi = {10.4230/LIPIcs.OPODIS.2019.25},
annote = {Keywords: Look-Compute-Move, Oblivious mobile robots, Robots with lights, Memory versus Communication, Moving and Computing}
}
|
Keywords: |
|
Look-Compute-Move, Oblivious mobile robots, Robots with lights, Memory versus Communication, Moving and Computing |
|
Collection: |
|
23rd International Conference on Principles of Distributed Systems (OPODIS 2019) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
11.02.2020 |
