On the Self-stabilization of Mobile Robots in Graphs

Lélia Blin 1 Maria Gradinariu Potop-Butucaru 2, 3 Sébastien Tixeuil 4, 5
2 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
4 GRAND-LARGE - Global parallel and distributed computing
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LIFL - Laboratoire d'Informatique Fondamentale de Lille, LRI - Laboratoire de Recherche en Informatique
Abstract : Self-stabilization is a versatile technique to withstand any transient fault in a distributed system. Mobile robots (or agents) are one of the emerging trends in distributed computing as they mimic autonomous biologic entities. The contribution of this paper is threefold. First, we present a new model for studying mobile entities in networks subject to transient faults. Our model differs from the classical robot model because robots have constraints about the paths they are allowed to follow, and from the classical agent model because the number of agents remains fixed throughout the execution of the protocol. Second, in this model, we study the possibility of designing self-stabilizing algorithms when those algorithms are run by mobile robots (or agents) evolving on a graph. We concentrate on the core building blocks of robot and agents problems: naming and leader election. Not surprisingly, when no constraints are given on the network graph topology and local execution model, both problems are impossible to solve. Finally, using minimal hypothesis with respect to impossibility results, we provide deterministic and probabilistic solutions to both problems, and show equivalence of these problems by an algorithmic reduction mechanism.
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00166547
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 8 août 2007 - 11:11:01
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:16:10

Fichiers

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

Identifiants

  • HAL Id : inria-00166547, version 2
  • ARXIV : 0708.0909

Citation

Lélia Blin, Maria Gradinariu Potop-Butucaru, Sébastien Tixeuil. On the Self-stabilization of Mobile Robots in Graphs. [Research Report] RR-6266, INRIA. 2007, pp.23. 〈inria-00166547v2〉

Partager

Métriques

Consultations de la notice

608

Téléchargements de fichiers

421