"Semi-Asynchronous": A new scheduler for robot based computing systems

The study of mobile entities, called robots, that have to accomplish global tasks on the basis of local information has attracted many researchers. A well-known scenario is that in which robots operate in Look-Compute-Move (LCM) computational cycles. In each cycle, a robot takes a snapshot of the environment (Look phase), then executes a distributed algorithm on the basis of the obtained snapshot (Compute phase), and finally moves toward a desired destination, if any (Move phase). LCM cycles might be subject to different temporal constraints dictated by the considered schedule. The classic models for the activation and synchronization of mobile robots are the fully-synchronous, semi-synchronous, and asynchronous models. The three models have been shown to constitute a hierarchy, that is fully-synchronous robots can accomplish more tasks than semi-synchronous robots that in turn can accomplish more tasks than asynchronous robots. The computational power of robots based on the different models has been extensively investigated, revealing a big gap between asynchronous robots and the other models. For many problems it is still not known whether the synchronization is crucial for designing resolution algorithms or not. In order to better understand the asynchronous case, here we propose further models referred to as semi-asynchronous, showing that for robots moving on graphs, semi-synchronous robots can accomplish more tasks than semi-asynchronous robots that in turn can accomplish more tasks than asynchronous robots. Whether the same strict hierarchy also holds for robots moving on the Euclidean plane remains open, however our investigation reveals interesting consequences that may help in better characterizing the computational power of robots with respect to the different synchronization models.