Wait-Free Gathering Without Chirality

We consider the problem of gathering

n

autonomous robots that evolve in a 2-dimensional Euclidian space at a single location, not known beforehand. We suppose the robots operate in the semi-synchronous Look-Compute-Move model and are anonymous, oblivious, and disoriented.

When robots are capable of strong multiplicity detection (that is, sensing the number of robots at a given location) and the initial configuration is not bivalent, the problem is known to be deterministically solvable for

n

 > 2 robots. When an arbitrary number

f

 < 

n

of robots may crash, recent results achieve deterministic gathering of correct robots in the classical model, assuming robots agree on a global common chirality (that is all robots have the same notion of left and right), leaving open the necessity of this assumption.

In this paper, we answer negatively to this question. Our approach is constructive: we present a deterministic gathering algorithm that admits an arbitrary number of crashes and gathers all correct robots even if they do not have a common chirality.