The power of lights: Synchronizing asynchronous robots using visible bits

In this paper we study the power of using lights, i.e. visible external memory, for distributed computation by autonomous robots moving in Look-Compute-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.