Gathering
Robots must meet at a single point that is not fixed in advance, and stay there.
Problem statement and measuresexpand
\(n\) robots start at distinct points and must all reach the same point in finite time and remain there. For \(n = 2\) the problem is called rendezvous. Time is counted in rounds (FSYNC, SSYNC) or in epochs (ASYNC: intervals in which every robot completes at least one full Look–Compute–Move cycle); colours count light colours.
Measures: Time, rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known; Colours, colours of the light per robot (0 for oblivious robots).
Self-stabilizing gathering, full lights, SSYNC, strong multiplicity detection
verifiedWith 2 colours and strong multiplicity detection, any number of robots gather in SSYNC with rigid moves from any configuration and any initial colours; one colour (oblivious robots) does not suffice.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Body: point
- Each robot is a point of the plane: several robots may share a point (multiplicity), and a robot hides only what lies exactly behind it on a line of sight.
- Visibility: unlimited visibility
- A robot sees all robots (subject to opacity).
- Opacity: transparent
- Robots do not obstruct each other's view.
- Faults: no faults
- All robots follow the algorithm forever.
- Scheduler: SSYNC
- SSYNC: time is divided into rounds; in each round a non-empty subset of robots, chosen by a fair adversary, executes one atomic Look–Compute–Move cycle. Called Atom by Prencipe Prencipe 2007.
- Lights (persistent memory): lights (LUMI)
- LUMI: each robot has a light with \(c\) colours, set at the end of Compute, visible to all robots including itself; it is both memory and communication. Also called luminous robots, or a full light.
- Agreement on coordinates: disoriented
- Each robot \(r\) observes in its own coordinate system, obtained from the global one by an unknown similarity (translation, rotation, uniform scaling, and possibly reflection); systems may differ between robots and, in some models, between cycles. Papers that call robots disoriented do not always mean this: Défago and Souissi use the word while assuming chirality Défago & Souissi 2008. Some papers also let the adversary change a robot's rotation, reflection and unit at every Look (variable disorientation) Flocchini et al. 2023 Wada et al. 2026.
- Movement: rigid
- Every Move phase ends at the computed destination.
- Multiplicity detection: strong multiplicity
- A snapshot is a multiset: each occupied point comes with the exact number of robots on it.
- Randomness: deterministic
- The destination computed in a cycle is a function of the snapshot (and the light, if any).
- Identifiers: anonymous
- Robots are indistinguishable and run the same algorithm.
- Number of robots: any \(n\)
- Any number \(n\ge 2\) of robots.
- Initial configurations: any start
- The algorithm must gather from every initial configuration from which gathering is possible at all in the setting; configurations proved unsolvable there (for example bivalent ones, or several multiplicities with weak detection and crashes) are excluded by the problem, not by the algorithm.
Statement for this variant
The robots start from an arbitrary configuration with arbitrary colours: several robots may share a point (a multiplicity), and the configuration may be bivalent, with \(n/2\) robots on each of two points. An algorithm that gathers from every such start is self-stabilizing Bonnet et al. 2026a.
What is known
- \(n = 2\): two oblivious robots at distinct points cannot gather in SSYNC (Theorem 3.1 of Suzuki & Yamashita 1999), already with rigid moves and common handedness; with two robots, multiplicity detection gives no information
- for every even \(n\) from a bivalent configuration, oblivious robots cannot gather in SSYNC, by a proof certified in Coq by Courtieu, Rieg, Tixeuil and Urbain (IPL 2015), as reported by Bonnet et al. 2026a
Results, in order of publication
Introductory and current best (the final theorem of the Coq development, Section 4.4 of the SIROCCO 2025 version): any \(n\), deterministic, no chirality, any initial positions and colours; the proof is certified in the Coq proof assistant. The authors call it the first fully self-stabilizing deterministic uniform gathering algorithm in SSYNC.
Open questions
Does self-stabilizing gathering with 2 colours extend to ASYNC Bonnet et al. 2026a?
Is self-stabilizing SSYNC gathering with lights solvable with weak or no multiplicity detection, or with non-rigid moves? The algorithm of Bonnet et al. 2026a uses strong multiplicity detection and rigid moves.
Notes
Bonnet, Bramas, Courtieu, Défago, Rieg, Tixeuil and Urbain call a bivalent configuration colour-bivalent when each of its two points holds as many White as Black robots. There, an activated White robot moves to the midpoint and turns Black, and an activated Black robot turns White without moving. In a bivalent configuration that is not colour-bivalent, every activated robot moves to the point with more Black robots. In any other configuration the robots run the oblivious SSYNC algorithm of Courtieu, Rieg, Tixeuil and Urbain (DISC 2016), which never creates a bivalent configuration; lights do not change there. The proof uses the Pactole library and a measure that decreases whenever a robot changes its state (Section 4.2). Earlier deterministic self-stabilizing SSYNC solutions for any \(n\) were for oblivious robots with odd \(n\) (Dieudonné and Petit), or used randomization Défago et al. 2020 or two different algorithms Asahiro & Yamashita 2025; the 2-colour SSYNC algorithm of Terai et al. 2023 needs all robots to start with the same colour (all as reported by Bonnet et al. 2026a). Checked against the full text of the SIROCCO 2025 version (model in Section 2, final theorem in Section 4.4) and of Suzuki & Yamashita 1999 (Theorem 3.1). The journal version presents two certified algorithms and was not read.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.