Stand-Up Indulgent Gathering on Lines - Sorbonne Université Access content directly
Conference Papers Year : 2023

Stand-Up Indulgent Gathering on Lines


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-04232951 , version 1 (09-10-2023)



Quentin Bramas, Sayaka Kamei, Anissa Lamani, Sébastien Tixeuil. Stand-Up Indulgent Gathering on Lines. SSS 2023: Stabilization, Safety, and Security of Distributed Systems, Oct 2023, Jersey City, NJ, United States. pp.451-465, ⟨10.1007/978-3-031-44274-2_34⟩. ⟨hal-04232951⟩
15 View
0 Download



Gmail Facebook X LinkedIn More