On Gathering of Semi-synchronous Robots in Graphs

We consider the Gathering problem where a swarm of weak robots disposed on the vertices of an anonymous graph are required to meet at one vertex from where they do not move anymore. In our recent work [Cicerone et al., SIROCCO’19], we have shown how synchronicity heavily affects the design of resolution algorithms within the standard Look-Compute-Move (LCM) model. In particular, we have investigated two dense and highly symmetric topologies: complete graphs and complete bipartite graphs. We characterized all solvable configurations for synchronous robots, whereas it is known that in complete graphs asynchronous robots cannot solve the problem, ever. Instead of approaching directly the asynchronous case in complete bipartite graphs, we asked what happens in the so-called semi-synchronous model, that is robots are synchronized but they are not necessarily all active within all LCM cycles. It turns out that still the gathering can never be accomplished on complete graphs, whereas challenging cases arise in complete bipartite graphs. We provide a distributed algorithm solving the problem for a wide set of possible configurations. For most of the remaining ones instead we provide impossibility results and a few of ad hoc resolution algorithms studied for very specific cases. Over all, still a full characterization is missing but our study points out how difficult might be to derive a general argument that catches all peculiarities. Moreover, some of our approaches reveal new insights that might be very useful for the resolution of other tasks.