Optimal byzantine resilient convergence in oblivious robot networks

Zohir Bouzid 1, * Maria Potop-Butucaru 1, 2 Sébastien Tixeuil 1, 3
* Auteur correspondant
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 : Given a set of robots with arbitrary initial location and no agreement on a global coordinate system, convergence requires that all robots asymptotically approach the exact same, but unknown beforehand, location. Robots are oblivious--- they do not recall the past computations --- and are allowed to move in a one-dimensional space. Additionally, robots cannot communicate directly, instead they obtain system related information only via visual sensors. We draw a connection between the convergence problem in robot networks, and the distributed \emph{approximate agreement} problem (that requires correct processes to decide, for some constant $\epsilon$, values distance $\epsilon$ apart and within the range of initial proposed values). Surprisingly, even though specifications are similar, the convergence implementation in robot networks requires specific assumptions about synchrony and Byzantine resilience. In more details, we prove necessary and sufficient conditions for the convergence of mobile robots despite a subset of them being Byzantine (i.e. they can exhibit arbitrary behavior). Additionally, we propose a deterministic convergence algorithm for robot networks and analyze its correctness and complexity in various synchrony settings. The proposed algorithm tolerates f Byzantine robots for (2f+1)-sized robot networks in fully synchronous networks, (3f+1)-sized in semi-synchronous networks. These bounds are optimal for the class of cautious algorithms, which guarantee that correct robots always move inside the range of positions of the correct robots.
Type de document :
Rapport
[Research Report] 2009, pp.15
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00387525
Contributeur : Maria Potop-Butucaru <>
Soumis le : lundi 25 mai 2009 - 15:35:47
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : jeudi 10 juin 2010 - 21:46:48

Fichiers

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

Identifiants

  • HAL Id : inria-00387525, version 1
  • ARXIV : 0905.3967

Collections

Citation

Zohir Bouzid, Maria Potop-Butucaru, Sébastien Tixeuil. Optimal byzantine resilient convergence in oblivious robot networks. [Research Report] 2009, pp.15. 〈inria-00387525〉

Partager

Métriques

Consultations de la notice

386

Téléchargements de fichiers

460