Skip to Main content Skip to Navigation
Conference papers

How to gather asynchronous oblivious robots on anonymous rings

Gianlorenzo d'Angelo 1, 2 Gabriele Di Stefano 1 Alfredo Navarra 3 
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A set of robots arbitrarily placed on different nodes of an anonymous ring have to meet at one common node and remain in there. This problem is known in the literature as the gathering. Anonymous and oblivious 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 asynchronous among robots. Moreover, each robot is empowered by the so called multiplicity detection capability, that is, it 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 ungatherable configurations. It is worth noting that our new algorithm makes use of a unified and general strategy for any initial configuration, even those left open by previous works.
Document type :
Conference papers
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Gianlorenzo D'Angelo Connect in order to contact the contributor
Submitted on : Friday, September 7, 2012 - 10:56:20 AM
Last modification on : Saturday, June 25, 2022 - 11:08:44 PM
Long-term archiving on: : Saturday, December 8, 2012 - 3:40:24 AM


Files produced by the author(s)


  • HAL Id : hal-00728979, version 1



Gianlorenzo d'Angelo, Gabriele Di Stefano, Alfredo Navarra. How to gather asynchronous oblivious robots on anonymous rings. 26th International Symposium on Distributed Computing (DISC 2012), Oct 2012, Salvador, Brazil. pp.330-344. ⟨hal-00728979⟩



Record views


Files downloads