Byzantine Convergence in Robots Networks: The Price of Asynchrony - Archive ouverte HAL Access content directly
Reports (Technical Report) Year : 2009

Byzantine Convergence in Robots Networks: The Price of Asynchrony

(1) , (2) , (1)
1
2
Zohir Bouzid
  • Function : Author
  • PersonId : 860591
Sébastien Tixeuil

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.
Fichier principal
Vignette du fichier
convergence.pdf (261.57 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

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

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More