Skip to Main content Skip to Navigation
Journal articles

Self-stabilizing robots in highly dynamic environments

Abstract : This paper deals with the classical problem of exploring a ring by a cohort of synchronous robots. We focus on the perpetual version of this problem in which it is required that each node of the ring is visited by a robot infinitely often.The challenge in this paper is twofold. First, we assume that the robots evolve in a highly dynamic ring, i.e., edges may appear and disappear unpredictably without any recurrence, periodicity, or stability assumption. The only assumption we made (known as the temporal connectivity assumption) is that each node is infinitely often reachable from any other node. Second, we aim at providing a self-stabilizing algorithm to the robots, i.e., the algorithm must guarantee an eventual correct behavior regardless of the initial state and positions of the robots.In this harsh environment, our contribution is to fully characterize, for each size of the ring, the necessary and sufficient number of robots to solve deterministically the problem.
Complete list of metadata

https://hal.inria.fr/hal-02413327
Contributor : Accord Elsevier Ccsd Connect in order to contact the contributor
Submitted on : Friday, October 22, 2021 - 7:01:16 PM
Last modification on : Monday, December 6, 2021 - 5:12:03 PM

File

S0304397518307163.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial 4.0 International License

Identifiers

Citation

Marjorie Bournat, Ajoy Datta, Swan Dubois. Self-stabilizing robots in highly dynamic environments. Theoretical Computer Science, Elsevier, 2019, 772, pp.88-110. ⟨10.1016/j.tcs.2018.11.026⟩. ⟨hal-02413327⟩

Share

Metrics

Record views

137

Files downloads

50