Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Optimal Byzantine Resilient Convergence in Asynchronous Robot Networks

Zohir Bouzid 1 Maria Potop-Butucaru 2 Sébastien Tixeuil 3, 1 
1 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
2 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
3 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : We propose the first deterministic algorithm that tolerates up to $f$ byzantine faults in $3f+1$-sized networks and performs in the asynchronous CORDA model. Our solution matches the previously established lower bound for the semi-synchronous ATOM model on the number of tolerated Byzantine robots. Our algorithm works under bounded scheduling assumptions for oblivious robots moving in a uni-dimensional space.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Maria Potop-Butucaru Connect in order to contact the contributor
Submitted on : Tuesday, June 2, 2009 - 10:54:22 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:39 AM
Long-term archiving on: : Friday, June 11, 2010 - 12:14:29 AM


Files produced by the author(s)


  • HAL Id : inria-00390870, version 1
  • ARXIV : 0906.0651


Zohir Bouzid, Maria Potop-Butucaru, Sébastien Tixeuil. Optimal Byzantine Resilient Convergence in Asynchronous Robot Networks. [Research Report] ???. 2009, pp.15. ⟨inria-00390870⟩



Record views


Files downloads