Byzantine Convergence in Robots Networks: The Price of Asynchrony

Abstract : 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.
Type de document :
Rapport
[Technical Report] 2009, pp.22
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00408881
Contributeur : Zohir Bouzid <>
Soumis le : mardi 4 août 2009 - 01:11:27
Dernière modification le : jeudi 22 novembre 2018 - 14:31:12
Document(s) archivé(s) le : mardi 15 juin 2010 - 19:26:52

Fichiers

convergence.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Citation

Zohir Bouzid, Maria Potop-Butucaru, Sébastien Tixeuil. Byzantine Convergence in Robots Networks: The Price of Asynchrony. [Technical Report] 2009, pp.22. 〈inria-00408881〉

Partager

Métriques

Consultations de la notice

572

Téléchargements de fichiers

131