How to gather asynchronous oblivious robots on anonymous rings

Résumé : 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.
Type de document :
Rapport
[Research Report] RR-7963, INRIA. 2012, pp.24
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00697132
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : lundi 14 mai 2012 - 15:54:05
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : jeudi 15 décembre 2016 - 07:15:08

Fichier

RR-7963.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00697132, version 1

Collections

Citation

Gianlorenzo D'Angelo, Gabriele Di Stefano, Alfredo Navarra. How to gather asynchronous oblivious robots on anonymous rings. [Research Report] RR-7963, INRIA. 2012, pp.24. 〈hal-00697132〉

Partager

Métriques

Consultations de la notice

502

Téléchargements de fichiers

164