Asynchronous Indulgent Gathering of Opaque Robots

arXiv:2509.10711v2 Announce Type: replace-cross Abstract: We consider the benchmarking problem of gathering in an (N,f)-fault system consisting of N robots, of which at most f may fail at any execution. The {em traditional} version asks N-f non-faulty robots to gather at a point not known a priori. The recently studied {em indulgent} version asks N-f non-faulty robots to gather at the location of a faulty one. Indulgent gathering is impossible in a (2,1)-crash system in the LUMI model under semi-synchrony, even when infinitely many colors and coordinate axis agreement are available. In this paper, we establish four results for indulgent gathering under asynchrony in LUMI, considering a {em mobility fault} model in which a robot crash only impacts its mobility but not the operation of the light. We first show that indulgent gathering is impossible in a (2,1)-mobility system using 2-colored lights, and then give an optimal solution w.r.t. the number of colors using 3-colored lights. We then give two deterministic algorithms for an (N,f)-mobility system, f<N, N,f unknown, that exhibit a nice time-color trade-off: One with time O(N) using 7-colored lights and another with time O(max{ell,f}) using 26-colored lights, where ell< N is the number of distinct convex layers of robot positions in the initial configuration. Our algorithms for an (N,f)-mobility system are the first to be analysed time complexity, can withstand obstructed visibility (opaque robot model) and asynchronous scheduling. Interestingly, our algorithms also solve traditional gathering.

Source: arXiv cs.RO | 2026-10-16