Gathering of robots in a ring with mobile faults

This paper studies the well-known problem of multiple mobile agents moving in a graph, but unlike previous results, we consider the problem in the presence of an adversarial mobile entity which we call the . The malicious entity can occupy any empty node and prevent honest mobile agents from entering this node. This new adversarial model is interesting as it models transient mobile faults that can appear anywhere in a network. Moreover, our model lies between the less powerful , where the adversary can block an agent for only a finite time, and the more powerful but static fault model of that can even destroy the agents.We study the problem for ring networks and we provide a complete characterization of the solvability of gathering, depending on the size of the ring and the number of agents . We consider both oriented or unoriented rings with either synchronous or asynchronous agents. We prove that in an unoriented ring network with asynchronous agents the problem is not solvable when is even, while for synchronous agents the problem is unsolvable when both is odd and is even. We then present algorithms that solve gathering for all the remaining cases, thus completely solving the problem. Finally, we provide a proof-of-concept implementation of the synchronous algorithms using programmable Lego Mindstorms EV3 robots.