Home›Mobile robots in the plane›Symmetry breaking and spreading›Leader election in the plane

Leader election in the plane

Anonymous robots must agree on one of them, using only their positions.

Problem statement and measurescollapse

Leader election: anonymous robots at distinct points must agree on one robot, each deciding from its own snapshot, without moving. With chirality: draw the smallest enclosing circle, a ray from its centre \(O\) through every robot, read the configuration clockwise from each ray as a word (distances along the ray, angle to the next ray); the ray with the unique smallest word carries the leader, its robot nearest \(O\). A leader can be elected exactly when this word is unique, that is, when the configuration has no rotational symmetry Dieudonné et al. 2013.

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

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine \(n\) identical drones hovering at different spots in a field. They carry no name tags, they cannot talk, and each one has its own private idea of which way is north, what counts as one metre, and possibly even which way is clockwise. In the problem the drones are robots, points at distinct places in the plane, and a robot's private north, unit of length and sense of clockwise form its local coordinate system. Each robot takes a snapshot, a photograph of where all the robots are in its local coordinate system, and, using the same program as every other robot, must decide "I am the leader" or "I am not", so that exactly one robot says yes; that robot is the leader. The robots are anonymous (they look the same and run the same program) and disoriented (no shared compass, unit of length or, without chirality, shared sense of clockwise). The question is: for which configurations (arrangements of the robots' positions) can this be done at all?

1AlgorithmRead the configuration as a word around the smallest enclosing circle Disoriented robots, with or without chirality → Dieudonné et al. 2013

This is the version where the robots agree on clockwise (chirality).

Draw the smallest circle that encloses all robots, the smallest enclosing circle; every robot finds the same circle. Call its centre \(O\). If a robot sits exactly at \(O\), it is the leader; stop.
Draw a ray (a half-line) from \(O\) through every robot (several robots may share a ray).
For each ray, list the distances between consecutive robots on it, starting from \(O\), measured as fractions of the circle's radius (so the private unit of length does not matter).
Starting at a ray and walking clockwise around the circle, write down a word: the list for this ray, then the angle to the next ray, then the list for the next ray, and so on, once around.
Every robot computes the word of every ray and picks the ray whose word is alphabetically smallest. If only one ray has that word, the leader is the robot on that ray nearest to \(O\).

Why it works and what it costs. All robots compute the same words, because everything is measured relative to the circle and the shared clockwise direction, so they all pick the same robot. The words of different rays are rotations of one another; two rays can have the same word only if turning the whole picture around \(O\) moves one ray onto the other, that is, if the configuration has rotational symmetry. Dieudonné et al. 2013 prove that this is the exact borderline: with chirality, a leader can be elected exactly when the smallest word is unique (they phrase it with Lyndon words), and they give a similar but more delicate rule, reading in both directions, when robots do not share clockwise.

Why it matters. Turning a picture into a word and comparing words is the standard way robot papers break symmetry, and electing a leader this way is the first step of arbitrary pattern formation Dieudonné et al. 2010.

2ImpossibilitySymmetric pictures look the same to everybody Disoriented robots, with or without chirality → Dieudonné et al. 2013

Place six robots at the corners of a regular hexagon. The adversary (an imagined opponent who chooses everything the algorithm does not control, here the robots' private coordinate systems) gives each robot a local coordinate system whose north points from the centre through that robot, and the same unit and handedness for all. Now every robot's snapshot is literally the same list of coordinates. The same happens for any \(n = 2\): two points are always swapped by a half-turn around their midpoint.

Why it holds. A deterministic program (no coin flips) that receives the same input gives the same output. So either every robot declares itself leader or none does; exactly one is impossible. The same argument works for any configuration that some rotation maps onto itself while moving robots, which is why the characterisation of Dieudonné et al. 2013 is phrased in terms of symmetry.

Why it matters. Almost every impossibility for robots in the plane, from pattern formation to gathering, is this argument: build a symmetric start and choose coordinate systems so that symmetric robots see identical snapshots.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Colours

Disoriented robots, with or without chirality standard

Whether anonymous robots can agree on a leader from their positions is characterised by Lyndon words around the smallest enclosing circle.

unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry

tight \(0\) vs —

Transparent fat robots, no chirality

Transparent fat robots without chirality can agree on an ordering, and so on a leader, exactly when their configuration is asymmetric.

unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry breaking

tight \(0\) vs —

What the community started looking at

Leader election in the plane was asked as a characterisation of the configurations from which anonymous robots can agree on one of them Dieudonné et al. 2013; its importance comes from its equivalence with arbitrary pattern formation Dieudonné et al. 2010 Cicerone et al. 2019.

Perspectives

Symmetry is the adversary Identical agents running the same deterministic program can be kept in lockstep forever. Across graphs, the plane and programmable matter, the papers break this symmetry with identifiers, with randomness, with asymmetric starts, or with the scheduler, and leader election keeps reappearing as the common core.
Weak robots in the plane Why the theory of robots in the plane starts from oblivious, anonymous, disoriented points; how formation problems became its testbed and the scheduler its adversary; and how a light with a few colours turned into memory, communication and a measure.
From robots to particles Programmable matter re-asks the questions of robots in the plane on a lattice, with particles that touch, remember a little and stay connected; SILBOT takes memory and messages away again, and the stochastic approach replaces algorithms by a biased local rule.

All settings

The assumption tree (2 settings, 1 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Colours); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Body › Visibility › Opacity › Faults › Scheduler › Lights (persistent memory) › Agreement on coordinates › Movement › Multiplicity detection › Randomness › Identifiers.

tight near-optimal polynomial gap unknown impossible no variant

No assumptions · 2 branches by body Nothing is assumed on any axis.
- +point+unlimited visibility+transparent+no faults
  Disoriented robots, with or without chirality standard setting Whether anonymous robots can agree on a leader from their positions is characterised by Lyndon words around the smallest enclosing circle.
- fat+unlimited visibility+transparent
  Transparent fat robots, no chirality Transparent fat robots without chirality can agree on an ordering, and so on a leader, exactly when their configuration is asymmetric.

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