Mobility Matters
Home›Mobile robots in the plane›Formation problems›Pattern formation›k-grouping›Gathering

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).

no assumptions›+ point›+ unlimited visibility›+ transparent›+ crash faults›+ SSYNC›oblivious, disoriented, non-rigid, + weak multiplicity, + \(n \ge 3\)

Crash faults, SSYNC

verified
Time: unknownColours: tight

With weak multiplicity detection and no common orientation, the correct robots gather despite up to \(n-1\) crashes.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Visibilityunlimited+Opacitytransparent: every robot sees every robot within range+Faultsup to \(f\) robots may crash+Schedulersemi-synchronous (SSYNC)+Multiplicity detectionweak: a robot sees whether a point holds more than one robot+Number of robots\(n \ge 3\)

Not assumed

Lights (persistent memory)oblivious, no light (OBLOT)Agreement on coordinatesno agreement on local coordinate systemsMovementnon-rigid: the adversary may stop a move after some minimum distance \(\delta\)RandomnessdeterministicIdentifiersanonymous: all robots are identicalInitial configurationsevery solvable initial configuration
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: crash faults
Up to \(f\) robots stop forever at adversarial times and remain visible at their last position.
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): oblivious
OBLOT: a robot's computation depends only on the current snapshot; nothing persists across cycles.
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: non-rigid
In a Move phase the adversary may stop a robot before its destination, but only after it has travelled at least \(\delta>0\) (a constant unknown to the robots) or reached the destination.
Multiplicity detection: weak multiplicity
A snapshot marks each occupied point as holding one robot or more than one.
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: \(n \ge 3\)
\(n\ge 3\) 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.

What is known

Time · rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known
unknown
Time not analysed.
lower bound
\(\text{impossible}\) Pattanayak et al. 2019b
bottleneckindistinguishable multiplicities
holds when
  • from a configuration with more than one multiplicity, no wait-free deterministic algorithm gathers with weak multiplicity detection (Theorem 1)
  • the paper shows its model is minimal: relaxing the capabilities further makes gathering impossible
introductory
\(\text{finite}\)
one crashcommon chirality\(n \ge 3\)a Look returns a multiset (multiplicities are seen)initial configuration with at most one point with a multiplicity
current best
\(\text{finite}\)
\(f \le n-1\)initial configurations with at most one multiplicity, which Theorem 1 shows necessary with weak detection
Colours · colours of the light per robot (0 for oblivious robots)
tight
No colours.
lower boundnone known
introductory
\(0\)
one crashcommon chirality\(n \ge 3\)a Look returns a multiset (multiplicities are seen)initial configuration with at most one point with a multiplicity
current best
\(0\)
\(f \le n-1\)initial configurations with at most one multiplicity, which Theorem 1 shows necessary with weak detection

Results, in order of publication

Agmon & Peleg 2006 introductory
Time \(\text{finite}\)Colours \(0\)
one crashcommon chirality\(n \ge 3\)a Look returns a multiset (multiplicities are seen)initial configuration with at most one point with a multiplicity

Theorem 3.8, SSYNC, non-rigid moves of at least a fixed distance \(S\); checked against the full text.

Bouzid et al. 2013 also
Time \(\text{finite}\)Colours \(0\)
strong multiplicity detectionchiralityany \(f < n\)initial configuration not bivalent

Wait-free; every initial configuration except the bivalent one (two points holding \(n/2\) robots each), from which gathering is impossible.

Bramas & Tixeuil 2015 also
Time \(\text{finite}\)Colours \(0\)
strong multiplicity detectionno chirality\(f \le n-1\)initial configuration not bivalent

Wait-free without chirality, in SSYNC with non-rigid moves (minimum distance \(\delta\)), from every configuration that is not bivalent. Checked against the full text.

Pattanayak et al. 2019b current best
Time \(\text{finite}\)Colours \(0\)
\(f \le n-1\)initial configurations with at most one multiplicity, which Theorem 1 shows necessary with weak detection

Wait-free (Theorem 2), weak multiplicity detection, no agreement on coordinates. The ASYNC algorithm of the same paper is in the setting with a restricted start.

Open questions

  1. "The maximum number of faults under which a solution is still feasible, for gathering and other tasks, has yet to be established" Agmon & Peleg 2006, in particular in ASYNC.

What carries over from neighbouring settings

Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.

Algorithms from weaker settings work here

Byzantine faults, SSYNC

Lower bounds from stronger settings hold here

No catalogued stronger setting.

Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.