文章基本信息

标题：On Memory, Communication, and Synchronous Schedulers When Moving and Computing
本地全文：下载
作者：Paola Flocchini ; Nicola Santoro ; Koichi Wada 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：153
页码：1-17
DOI：10.4230/LIPIcs.OPODIS.2019.25
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Look-Compute-Move; Oblivious mobile robots; Robots with lights; Memory versus Communication; Moving and Computing