Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Fault and Byzantine Tolerant Self-stabilizing Mobile Robots Gathering

Abstract : Gathering is a fundamental coordination problem in cooperative mobile robotics. In short, given a set of robots with \emph{arbitrary} initial locations and no initial agreement on a global coordinate system, gathering requires that all robots, following their algorithm, reach the exact same but not predetermined location. Gathering is particularly challenging in networks where robots are oblivious (i.e.,~stateless) and direct communication is replaced by observations on their respective locations. Interestingly any algorithm that solves gathering with oblivious robots is inherently self-stabilizing if no assumption is made on the initial distribution of the robots. In this paper, we significantly extend the studies of deterministic gathering feasibility under different assumptions related to synchrony and faults (crash and Byzantine). Unlike prior work, we consider a larger set of scheduling strategies, such as bounded schedulers, and derive interesting lower bounds on these schedulers. In addition, we extend our study to the feasibility of probabilistic self-stabilizing gathering in both fault-free and fault-prone environments.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Maria Potop-Butucaru Connect in order to contact the contributor
Submitted on : Saturday, October 27, 2012 - 12:03:07 AM
Last modification on : Sunday, June 26, 2022 - 11:57:17 AM
Long-term archiving on: : Saturday, December 17, 2016 - 6:00:56 AM


Files produced by the author(s)


  • HAL Id : hal-00746087, version 1
  • ARXIV : 1602.05546


Julien Clement, Xavier Défago, Maria Gradinariu Potop-Butucaru, Stephane Messika, Philippe Raipin-Parvedy. Fault and Byzantine Tolerant Self-stabilizing Mobile Robots Gathering. 2012. ⟨hal-00746087⟩



Record views


Files downloads