| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2020-05-09 17:26 On Memory, Communication, and Synchronous Schedulers for Autonomous Mobile Robots Paola Flocchini (UoO), Nicola Santoro (CU), Koichi Wada (HU)  COMP2020-3 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (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) |
| (in English) | Look-Compute-Move / Oblivious mobile robots / Robots with lights / Memory versus Communication / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 120, no. 13, COMP2020-3, pp. 17-24, May 2020. | |
| Paper # | COMP2020-3 | |
| Date of Issue | 2020-05-02 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | COMP2020-3 |
|
| Conference Information | |
| Committee | COMP IPSJ-AL |
| Conference Date | 2020-05-09 - 2020-05-09 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2020-05-COMP |
| Language | English |
| 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 |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 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) |
| 4th Author's Name | |
| 4th Author's Affiliation | () |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| 7th Author's Name | |
| 7th Author's Affiliation | () |
| 8th Author's Name | |
| 8th Author's Affiliation | () |
| 9th Author's Name | |
| 9th Author's Affiliation | () |
| 10th Author's Name | |
| 10th Author's Affiliation | () |
| 11th Author's Name | |
| 11th Author's Affiliation | () |
| 12th Author's Name | |
| 12th Author's Affiliation | () |
| 13th Author's Name | |
| 13th Author's Affiliation | () |
| 14th Author's Name | |
| 14th Author's Affiliation | () |
| 15th Author's Name | |
| 15th Author's Affiliation | () |
| 16th Author's Name | |
| 16th Author's Affiliation | () |
| 17th Author's Name | |
| 17th Author's Affiliation | () |
| 18th Author's Name | |
| 18th Author's Affiliation | () |
| Speaker | Author-3 |
| Date Time | 2020-05-09 17:26:00 |
| Presentation Time | 1 minutes |
| Registration for | COMP |
| Paper # | COMP2020-3 |
| Volume (vol) | vol.120 |
| Number (no) | no.13 |
| Page | pp.17-24 |
| #Pages | 8 |
| Date of Issue | 2020-05-02 (COMP) |
[Return to Top Page]