Stand-up indulgent gathering on lines - Sorbonne Université
Journal Articles Theoretical Computer Science Year : 2024

Stand-up indulgent gathering on lines

Abstract

We consider a variant of the crash-fault gathering problem called stand-up indulgent gathering (SUIG). In this problem, a group of mobile robots must eventually gather at a single location, which is not known in advance. If no robots crash, they must all meet at the same location. However, if one or more robots crash at a single location, all non-crashed robots must eventually gather at that location. The SUIG problem was first introduced for robots operating in a two-dimensional continuous Euclidean space, with most solutions relying on the ability of robots to move a prescribed (real) distance at each time instant. In this paper, we investigate the SUIG problem for robots operating in a discrete universe (i.e., a graph) where they can only move one unit of distance (i.e., to an adjacent node) at each time instant. Specifically, we focus on line-shaped networks and characterize the solvability of the SUIG problem for oblivious robots without multiplicity detection.

Dates and versions

hal-04683560 , version 1 (02-09-2024)

Identifiers

Cite

Quentin Bramas, Sayaka Kamei, Anissa Lamani, Sébastien Tixeuil. Stand-up indulgent gathering on lines. Theoretical Computer Science, 2024, 1016, pp.114796. ⟨10.1016/j.tcs.2024.114796⟩. ⟨hal-04683560⟩
39 View
0 Download

Altmetric

Share

More