Byzantine Convergence in Robots Networks: The Price of Asynchrony - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport Technique) Année : 2009

Byzantine Convergence in Robots Networks: The Price of Asynchrony

Zohir Bouzid
  • Fonction : Auteur
  • PersonId : 860591
Sébastien Tixeuil

Résumé

We study the convergence problem in fully asynchronous, uni-dimensional robot networks that are prone to Byzantine (i.e. malicious) failures. In these settings, oblivious anonymous robots with arbitrary initial positions are required to eventually converge to an a apriori unknown position despite a subset of them exhibiting Byzantine behavior. Our contribution is twofold. We propose a deterministic algorithm that solves the problem in the most generic settings: fully asynchronous robots that operate in the non-atomic CORDA model. Our algorithm provides convergence in 5f+1-sized networks where f is the upper bound on the number of Byzantine robots. Additionally, we prove that 5f+1 is a lower bound whenever robot scheduling is fully asynchronous. This constrasts with previous results in partially synchronous robots networks, where 3f+1 robots are necessary and sufficient.
Fichier principal
Vignette du fichier
convergence.pdf (261.57 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00408881 , version 1 (04-08-2009)

Identifiants

  • HAL Id : inria-00408881 , version 1
  • ARXIV : 0908.0390

Citer

Zohir Bouzid, Maria Potop-Butucaru, Sébastien Tixeuil. Byzantine Convergence in Robots Networks: The Price of Asynchrony. [Technical Report] ???. 2009, pp.22. ⟨inria-00408881⟩
419 Consultations
79 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More