8485 articles  [english version]

hal-00697132, version 1

How to gather asynchronous oblivious robots on anonymous rings

Gianlorenzo D'Angelo (, http://informatica.ing.univaq.it/dangelo/) 1, Gabriele Di Stefano 2, Alfredo Navarra a3

N° RR-7963 (2012)

Résumé : 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.

  • a –  Università degli Studi di Perugia
  • 1 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
  • INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
  • 2 :  University of L'Aquila [Italy] (UNIVAQ)
  • University of L'Aquila
  • 3 :  Dipartimento di Matematica e Informatica [Perugia] (DMI)
  • Università degli studi di Perugia
  • Domaine : Informatique/Algorithme et structure de données
  • Mots-clés : distributed algorithm – asynchronous system – gathering – oblivious robots
  • Référence interne : RR-7963
 
  • hal-00697132, version 1
  • oai:hal.inria.fr:hal-00697132
  • Contributeur : 
  • Soumis le : Lundi 14 Mai 2012, 15:54:05
  • Dernière modification le : Mardi 15 Mai 2012, 11:22:00