How to gather asynchronous oblivious robots on anonymous rings

Description

A set of robots arbitrarily placed on the nodes of an anonymous graph have to meet at one common node and remain in there. This problem is known in the literature as the \emph{gathering}. Robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move instantaneously (Move). Cycles are performed asynchronously for each robot. Moreover, each robot is empowered by the so called \emph{multiplicity detection} capability, that is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. The described problem has been extensively studied during the last years. However, the known solutions work only for specific initial configurations and leave some open cases. In this paper, we provide an algorithm which solves the general problem, and is able to detect all the non-gatherable configurations. It is worth noting that our new algorithm makes use of a unified and general strategy for any initial configuration.

Abstract (French)

Un ensemble de robots placés arbitrairement sur les sommets d'un graphe anonyme doivent se rencontrer sur un sommet commun. Ce problème est connu dans la littérature comme le \emph{gathering}. Les robots utilisent des cycles Look-Compute-Move; dans un cycle, un robot prend un instantané de la configuration actuelle (Look), décide de rester inactif ou de se déplacer sur l'un de ses voisins (Compute), et dans ce cas, fait le déplacement (Move). Les cycles sont exécutés de manière asynchrone pour chaque robot. Chaque robot possède la capacité de \emph{multiplicity detection}: un robot est capable de détecter au cours de son opération Look si un sommet est vide, occupé par un robot, ou occupé par un nombre indéfini de robots. Le problème décrit a été largement étudié au cours des dernières années. Toutefois, les solutions connues ne sont valides que pour des configurations initiales spécifiques. Nous fournissons un algorithme qui résout le problème général, et est capable de détecter toutes les configurations initiales pour lesquelles le problème est impossible. Il est intéressant de noter que notre nouvel algorithme utilise une stratégie unifiée et générale pour chaque configuration initiale.

Additional details