The Power of Lights: Synchronizing Asynchronous Robots Using Visible Bits
Authors:
- Shantanu DasSDShantanu Das
- Paola FlocchiniPFPaola Flocchini
- Giuseppe PrencipeGPGiuseppe Prencipe
- Nicola SantoroNSNicola Santoro
- Masafumi YamashitaMYMasafumi Yamashita
- 1 June 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636927,p. 506-515
Abstract
In this paper we study the power of using lights, i.e. visible external memory, for distributed computation by autonomous robots moving in LookCompute-Move (LCM) cycles. With respect to the LCM cycles, the most common models studied in the literature are the fully-synchronous (FSYNC), the semisynchronous (SSYNC), and the asynchronous (ASYNC). In this paper we introduce in the ASYNC model, the weakest of the three, the availability of visible external memory: each robot is equipped with a light bulb that is visible to all other robots, and that can display a constant numbers of different colors; the colors are persistent, that is they are not automatically reset at the end of each cycle. We first study the relationship between ASYNC with visible bits and SSYNC. We prove hat asynchronous robots, when equipped with a constant number of colors, are strictly more powerful than traditional semisynchronous robots. We also show that, when enhanced with visible lights, the difference between asynchrony and semi-synchrony disappears; this result must be contrasted with the strict dominance ASYNC <;SSYNC between the models without lights. We then study the relationship between ASYNC with visible bits and FSYNC. We prove that asynchronous robots with a constant number of visible bits, if they can remember a single snapshot, are strictly more powerful than fully-synchronous robots. This is to be contrasted with the fact that, without lights, ASYNC robots are not even as powerful as SSYNC, even if they remember an unlimited number of previous snapshots. These results demonstrate the power of using visible external memory for distributed computation with autonomous robots. In particular, asynchrony can be overcome with the power of lights.Keywords
This publication has 18 references indexed in Scilit:
- Brief Announcement: The BG-Simulation for Byzantine Mobile Robots2011
- Leader Election Problem versus Pattern Formation Problem2010
- SCATTER OF ROBOTSParallel Processing Letters, 2009
- Using eventually consistent compasses to gather memory-less mobile robots with limited visibilityACM Transactions on Autonomous and Adaptive Systems, 2009
- Circle formation of weak mobile robotsACM Transactions on Autonomous and Adaptive Systems, 2008
- Arbitrary pattern formation by asynchronous, anonymous, oblivious robotsTheoretical Computer Science, 2008
- Dynamic Compass Models and Gathering Algorithms for Autonomous Mobile Robots2007
- The Effect of Synchronicity on the Behavior of Autonomous Mobile RobotsTheory of Computing Systems, 2005
- Gathering of asynchronous robots with limited visibilityTheoretical Computer Science, 2005
- Coordination without communication: the case of the flocking problemDiscrete Applied Mathematics, 2004