Mobility Matters
Home›Programmable matter›Self-organising particle systems›Leader election in programmable matter

Leader election in programmable matter

Anonymous constant-memory particles must elect exactly one leader, which most shape-formation algorithms need first.

Problem statement and measurescollapse
LStart: every particle is eligibleRound 1: corners drop outRound 2: corners drop outRound 3: corners drop outFinal: one candidate left, the leader
Leader election by erosion on a configuration without holes: no particle moves. An eligible particle (blue) whose eligible neighbours are few and consecutive (none, one, two that are neighbours of each other, three in a row) is a corner and drops out (grey); corners drop out round after round, peeling the configuration from its boundary, until a single candidate remains and becomes the leader Di Luna et al. 2020 D'Angelo et al. 2020. Configurations with holes need other algorithms Derakhshandeh et al. 2015.

A connected configuration (the set of nodes occupied by particles) of \(n\) anonymous particles (initially contracted) must reach a state in which exactly one particle is the leader and all others know they are not. Time is in asynchronous rounds; \(L_{out}\) is the length of the outer boundary and \(D\) the diameter of the configuration.

Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).

A first look

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

Imagine a swarm of identical tiny machines, packed together on a floor tiled with triangles, that must pick one boss without any name tags. Each machine is a particle. It occupies one node of the triangular lattice, the infinite tiling of the plane by equilateral triangles whose corners are the nodes; particles on adjacent nodes are neighbours. A particle remembers only a few bits, and can read and write the memory of its neighbours. It moves in two steps: an expansion into an empty adjacent node, after which it briefly occupies both nodes, then a contraction into one of the two; so one expansion and one contraction move it by one node. In the standard version there are \(n\) particles whose nodes form one connected configuration, possibly with holes (empty regions enclosed by particles); all particles agree on what clockwise means (chirality), but not on a common north. An adversary, a scheduler that we assume chooses the worst order, decides when each particle acts; each time a particle acts is an activation, and a round is a stretch of time in which every particle has been activated at least once. The goal: exactly one particle ends in state leader, every other particle knows it is not, and we count the rounds this takes.

1AlgorithmErosion: peel the configuration from the outside Silent oblivious particles (SILBOT) → D'Angelo et al. 2020

This works on configurations without holes. It is the erosion of Di Luna et al. 2020, which D'Angelo et al. 2020 showed can be run even by particles with no memory and no messages. No particle changes its node (in the memoryless version, expansions serve as signals).

  1. Every particle starts as eligible.
  2. An eligible particle is a corner if its eligible neighbours are few and sit next to each other: none, one, two that are neighbours of each other, or three in a row.
  3. A corner drops out (becomes ineligible). Corners keep dropping out round after round, so the configuration is eaten from its outer boundary (the particles next to the empty outside; a hole has a boundary too) inwards, like a coastline eroded by the sea.
  4. A few special cases stop the peeling: a lone eligible particle, two eligible particles that are each other's only eligible neighbour, or a triangle of three, become candidates (for leader) instead of dropping out.
  5. At the end, 1, 2 or 3 candidates remain, each a neighbour of the others.
Why it works and what it costs. A hole-free configuration always has a corner, and removing corners never splits the eligible particles into parts or creates a hole, so erosion never gets stuck. Each removal leaves fewer eligible particles, and D'Angelo et al. 2020 show the process ends in \(O(n)\) rounds. It cannot always leave a single leader: three particles in a triangle look exactly alike (see the next idea). It also fails with holes: in a ring of particles around a hole, each particle has two eligible neighbours that are not neighbours of each other, so nobody is a corner. The best known result elects exactly one leader, holes allowed, deterministically in \(O(L_{out}+D)\) rounds, where \(L_{out}\) is the length of the outer boundary and \(D\) the diameter of the configuration Dufoulon et al. 2021.

Why it matters. Erosion is the first step of the deterministic shape-formation algorithm and is reused whenever a few candidate leaders are good enough.

2ImpossibilityThree identical particles in a triangle Stationary, chirality, weak scheduler → Chalopin et al. 2026

Take three particles forming a small triangle, and suppose particles never move and the scheduler may activate all three at the same moment. Each particle sees the same picture: two neighbours, one to its left and one to its right (they have chirality, so 'left' means the same to all). They start in the same state, so in their first activation they compute the same thing and write the same thing. After that activation they are again in identical states with identical views, and so on forever. Whatever a deterministic algorithm (one that flips no coins) does, either all three become leader or none does Chalopin et al. 2026.

Why it holds. The argument only uses symmetry: an algorithm cannot tell apart particles whose surroundings are rotated copies of each other. The same reasoning shows that a configuration with six-fold symmetry may end with six leaders, which is why stationary particles with chirality elect up to six leaders Bazzi & Briones 2019. To get exactly one leader, papers add something that breaks the symmetry: coin flips Derakhshandeh et al. 2015, a scheduler that activates one particle at a time Briones et al. 2023, or a common direction Chalopin et al. 2026.

Why it matters. Symmetry is the basic obstacle in all of programmable matter; it explains why results say 'at most three' or 'at most six' leaders.

3AlgorithmCoin flips along the boundaries Randomized, with chirality → Derakhshandeh et al. 2015

Only particles on a boundary (the outer boundary, or the boundary of a hole) take part. Each boundary closes on itself, and with chirality everyone walks it in the same direction.

  1. Every boundary particle starts as a candidate. Between two consecutive candidates lies a segment of non-candidates.
  2. Compare segments: a candidate whose segment ahead is shorter than the segment behind it gives up (particles compare lengths by passing tokens, one per particle).
  3. If all segments are equal, every candidate flips a coin. On heads it passes its candidacy forward to the next candidate's spot; when it does and the next candidate keeps its own, two candidacies land on one spot and merge.
  4. A candidate that is alone on its boundary checks whether it is the outer boundary (by adding up the turns along it; the outer boundary turns one full circle one way, the boundary of a hole the other way). Alone on the outer boundary: it is the leader. Alone on the boundary of a hole: it gives up.
Why it works and what it costs. There is always at least one candidate on the outer boundary, and while there are two or more, each phase removes one with probability at least \(1/4\), so the number of candidates keeps shrinking. Holes are no problem, because the boundary of a hole eventually loses all its candidates. The expected time is \(O(L_{max})\) rounds, \(L_{max}\) the length of the longest boundary Derakhshandeh et al. 2015; this was improved to \(O(n)\) rounds with high probability Daymude et al. 2017, and later matched without coins Dufoulon et al. 2021.

Why it matters. Working on boundaries instead of the whole configuration is the idea behind the fast algorithms that followed.

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
Moves
Deterministic, with chirality standard
Deterministic leader election in \(O(L_{out}+D)\) rounds, as fast as the best randomized algorithm, holes allowed.
unknown \(O(L_{out}+D)\) vs —
unknown — vs —
Randomized, with chirality
Randomized leader election in a linear number of rounds with high probability.
unknown \(O(n)\) vs —
unknown — vs —
Stationary, chirality, no holes
On hole-free configurations with chirality, stationary constant-memory particles elect a leader deterministically in \(O(n)\) rounds.
unknown \(O(n)\) vs —
tight — vs —
Deterministic, no orientation
Without chirality, a unique leader can still be elected deterministically, in \(O(L_{out}n^2)\) rounds.
polynomial gap \(O(L_{out}n^2)\) vs —
unknown — vs —
Stationary, common direction, no chirality
With one common direction and no chirality, a unique leader is elected without moving, with obstacles allowed, but only with implicit termination.
unknown \(O(n^3)\) vs \(\text{explicit termination impossible}\) symmetry breaking
tight — vs —
Stationary, fair scheduler, no orientation, no holes
Stationary constant-memory particles with no orientation and no chirality elect a unique leader from any initial memory: silent self-stabilising election on simply connected systems.
unknown \(\text{finite}\) vs —
tight — vs —
Stationary, chirality, weak scheduler
Without moving, particles with chirality elect at most six leaders in \(O(n^2)\) rounds, holes allowed.
unknown \(O(n^2)\) vs —
tight — vs —
Stationary, asynchronous, no orientation, no holes
Stationary particles with no common orientation elect a leader in connected, contractible 2D or 3D systems under an unfair asynchronous adversary; the running time there is not analysed.
unknown \(\text{finite}\) vs —
tight — vs —
Stationary, sequential, no orientation, no holes
Under an unfair sequential adversary, stationary particles with no common orientation elect a unique leader in \(O(n)\) rounds, in 2D or 3D.
unknown \(O(n)\) vs —
tight — vs —
SILBOT with holes
With holes, SILBOT particles cannot elect up to three leaders while staying connected; if they can tell a hole from the exterior, election with compaction takes \(O(n^2)\) rounds.
impossible \(O(n^2)\) vs \(\text{impossible}\) symmetry breaking
unknown — vs —
Silent oblivious particles (SILBOT)
Silent oblivious particles (SILBOT) elect at most three mutually adjacent leaders from hole-free configurations in \(O(n)\) rounds.
unknown \(O(n)\) vs —
unknown — vs —
Oblivious, common compass, holes allowed
Oblivious particles that agree on all directions elect a unique leader in connected configurations with holes, self-stabilising, using movement, under an unfair sequential scheduler.
unknown \(\text{finite}\) vs —
unknown — vs —

Open questions 5

Deterministic, with chirality

  1. Fast deterministic leader election under weaker (non-atomic) schedulers, and without letting the system disconnect Dufoulon et al. 2021.

Deterministic, no orientation

  1. Deterministic leader election without chirality in linear time.

Stationary, chirality, weak scheduler

  1. Is a unique leader ever impossible for stationary particles with chirality? Dufoulon et al. say this was shown in Bazzi & Briones 2019, at least for a weak scheduler Dufoulon et al. 2021; the theorem was not read.

Stationary, asynchronous, no orientation, no holes

  1. Deterministic leader election in \(O(L_{out}+D)\) rounds under a weaker scheduler Dufoulon et al. 2021.

SILBOT with holes

  1. Can SILBOT particles elect leaders from configurations with holes if the system may disconnect temporarily, without exterior awareness? The impossibility of D'Angelo et al. 2020 assumes that connectivity is preserved.

What the community started looking at

Leader election was the first task studied, because shape formation needs a leader Derakhshandeh et al. 2015. The first question was feasibility with constant memory, then rounds: randomized algorithms came first Derakhshandeh et al. 2015 Daymude et al. 2017, then deterministic ones without chirality Emek et al. 2019 and in linear time Dufoulon et al. 2021. Later work weakened the model in three directions: stationary particles Bazzi & Briones 2019 Chalopin et al. 2026, asynchronous adversaries Briones et al. 2023, and silent, oblivious particles D'Angelo et al. 2020; self-stabilising election with constant memory followed Chalopin et al. 2025 Chalopin et al. 2026.

Related problems

Leader election in the plane: Both elect a leader among anonymous entities from geometry alone; particles on the lattice can also move and talk to neighbours, robots in the plane only see Dufoulon et al. 2021.

Perspectives

  • Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
  • 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.
  • 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.
  • What forces the bounds Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.
  • The most consequential open problems Ten open questions ranked by how far a solution would propagate through the atlas, with the chain of problems each one feeds.

All settings

The assumption tree (12 settings, 5 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, Moves); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Memory › Scheduler › Orientation › Movement › Randomness › Initial shape › Connectivity during execution.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Movement

0stationary: particles never move1particles may move

The early leader-election algorithms for amoebots only exchanged messages, and "did not use the movement ability as an aid to the computation" Dufoulon et al. 2021. Emek et al. showed that movement lets particles elect a unique leader deterministically with no assumption on chirality or holes; the main idea is "the usage of the ability of the amoebots to move, which previous leader election algorithms have not used" Emek et al. 2019. The stationary setting stayed interesting because particles may be unable to move, "so as to maintain a configuration or due to the presence of obstacles" Chalopin et al. 2026. Bazzi and Briones studied stationary deterministic election Bazzi & Briones 2019, where symmetric configurations can force up to six leaders (as reported by Dufoulon et al. 2021). Chalopin, Das and Kokkou showed that one common direction suffices for a unique stationary leader Chalopin et al. 2026.

Formal definitions
0stationary
No particle ever expands or contracts; the configuration is fixed and only states change.
1may move
Particles may expand and contract during the election.

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