Skip to Main content Skip to Navigation

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.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Zohir Bouzid Connect in order to contact the contributor
Submitted on : Tuesday, August 4, 2009 - 1:11:27 AM
Last modification on : Friday, January 8, 2021 - 5:46:03 PM
Long-term archiving on: : Tuesday, June 15, 2010 - 7:26:52 PM


Files produced by the author(s)


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


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



Record views


Files downloads