| Presentation | 2020-05-09 On Memory, Communication, and Synchronous Schedulers for Autonomous Mobile Robots Paola Flocchini, Nicola Santoro, Koichi Wada, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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 $mathit{Look}$-$mathit{Compute}$-$mathit{Move}$ ($mathit{LCM}$) %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, $OB$, the robots are oblivious (no persistent memory) and silent (no explicit means of communication). In contrast, in the $LU$ model, each robot is equipped with a constant-sized persistent memory (called {em 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 $LU$: $FS$ where the robots have a constant-size persistent memory but are silent; and $FC$, where 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 FSY, while they are incomparable under the semi-synchronous scheduler SSY. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Look-Compute-Move / Oblivious mobile robots / Robots with lights / Memory versus Communication |
| Paper # | COMP2020-3 |
| Date of Issue | 2020-05-02 (COMP) |
| Conference Information | |
| Committee | COMP / IPSJ-AL |
|---|---|
| Conference Date | 2020/5/9(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | National Institute of Informatics |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| Vice Chair | Shinichi Nakano(Gunma Univ.) |
| Secretary | Shinichi Nakano(Nagoya Univ) / (Univ. of Hyogo) |
| Assistant | Kazuhisa Seto(Seikei Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On Memory, Communication, and Synchronous Schedulers for Autonomous Mobile Robots |
| Sub Title (in English) | |
| Keyword(1) | Look-Compute-Move |
| Keyword(2) | Oblivious mobile robots |
| Keyword(3) | Robots with lights |
| Keyword(4) | Memory versus Communication |
| 1st Author's Name | Paola Flocchini |
| 1st Author's Affiliation | University of Ottawa(UoO) |
| 2nd Author's Name | Nicola Santoro |
| 2nd Author's Affiliation | Carleton University(CU) |
| 3rd Author's Name | Koichi Wada |
| 3rd Author's Affiliation | Hosei University(HU) |
| Date | 2020-05-09 |
| Paper # | COMP2020-3 |
| Volume (vol) | vol.120 |
| Number (no) | COMP-13 |
| Page | pp.pp.17-24(COMP), |
| #Pages | 8 |
| Date of Issue | 2020-05-02 (COMP) |