Leader election in the plane
Anonymous robots must agree on one of them, using only their positions.
Problem statement and measuresexpand
\(n\) anonymous robots (identical, with no names) at distinct points must agree on a single robot (the leader), each deciding from its own snapshot.
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).
Transparent fat robots, no chirality
verifiedTime: unknownColours: tight
Transparent fat robots without chirality can agree on an ordering, and so on a leader, exactly when their configuration is asymmetric.
Assumed (added on the last edge are outlined)
+Visibilityunlimited+Opacitytransparent: every robot sees every robot within range
Not assumed
Bodyfat robots (unit discs)Faultsup to \(f\) Byzantine robotsSchedulerasynchronous (ASYNC)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\)Multiplicity detectionnone: a point with several robots looks like one robotRandomnessdeterministicIdentifiersanonymous: all robots are identical
Formal definitions of this setting
- Body: fat
- Each robot is a closed disc of radius 1 (unit disc). Discs may not overlap, so robots cannot share a point and must avoid collisions; a disc hides what lies behind it from other robots. Gathering then asks for a configuration whose union of discs is connected and in which every robot sees all others Czyzowicz et al. 2009.
- Visibility: unlimited visibility
- A robot sees all robots (subject to opacity).
- Opacity: transparent
- Robots do not obstruct each other's view.
- Faults: Byzantine
- Up to \(f\) robots move arbitrarily (adversarially); with lights, they may also set arbitrary colours.
- Scheduler: ASYNC
- ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may look while others move, and compute on an outdated snapshot. Time is counted in epochs: an epoch is an interval of time in which every robot completes at least one full Look–Compute–Move cycle; it need not be the shortest such interval. The execution is divided into consecutive epochs, and a bound of \(X\) epochs holds for every such division. In FSYNC and SSYNC time is counted in rounds. Called Corda by Prencipe Prencipe 2007. Intermediate variants restrict interleavings: LC-atomic (no Look by another robot between a robot's Look and its Compute), Move-atomic (no Look during another robot's Move) and CM-atomic Flocchini et al. 2023.
- 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 Masuzawa 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: no multiplicity detection
- A snapshot is a set of points: a point occupied by several robots looks like a single robot.
- 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.
What is known
Time · rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known
unknown
Solvable exactly on asymmetric configurations.
lower bound
\(\text{impossible}\) Chaudhuri & Mukhopadhyaya 2015
bottlenecksymmetry breaking
holds when
- symmetric configurations (Theorem 6)
- deterministic
introductory—
current best
\(\text{finite}\)
Colours · colours of the light per robot (0 for oblivious robots)
tight
No colours.
Results, in order of publication
Chaudhuri & Mukhopadhyaya 2015 current best
Time \(\text{finite}\)Colours \(0\)
Introductory and current best (Theorems 1–6, algorithm MakeAsym).
Open questions
None recorded for this variant.
Notes
Checked against the full text (arXiv 1208.4484).
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
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Disoriented robots, with or without chirality
Time \(\text{impossible}\)
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.