Skip to Main content Skip to Navigation
Journal articles

Convergence and covering on graphs for wait-free robots

Abstract : The class of robot convergence tasks has been shown to capture fundamental aspects of fault-tolerant computability. A set of asynchronous robots that may fail by crashing, start from unknown places in some given space, and have to move towards positions close to each other. In this article, we study the case where the space is uni-dimensional, modeled as a graph G. In graph convergence, robots have to end up on one or two vertices of the same edge. We consider also a variant of robot convergence on graphs, edge covering, where additionally, it is required that not all robots end up on the same vertex. Remarkably, these two similar problems have very different computability properties, related to orthogonal fundamental issues of distributed computations: agreement and symmetry breaking. We characterize the graphs on which each of these problems is solvable, and give optimal time algorithms for the solvable cases. Although the results can be derived from known general topology theorems, the presentation serves as a self-contained introduction to the algebraic topology approach to distributed computing, and yields concrete algorithms and impossibility results.
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.laas.fr/hal-01740338
Contributor : Matthieu Roy <>
Submitted on : Wednesday, March 21, 2018 - 7:13:19 PM
Last modification on : Thursday, June 10, 2021 - 3:02:59 AM
Long-term archiving on: : Thursday, September 13, 2018 - 7:11:49 AM

File

wait-free-robots.pdf
Publisher files allowed on an open archive

Identifiers

Citation

Armando Castañeda, Sergio Rajsbaum, Matthieu Roy. Convergence and covering on graphs for wait-free robots. Journal of the Brazilian Computer Society, Springer Verlag, 2018, 24 (1), ⟨10.1186/s13173-017-0065-8⟩. ⟨hal-01740338⟩

Share

Metrics

Record views

223

Files downloads

267