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 measuresexpand

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

no assumptions›+ constant memory›weak scheduler, + chirality

Stationary, chirality, weak scheduler

verified
Time: unknownMoves: tight

Without moving, particles with chirality elect a unique leader unless the configuration is \(k\)-symmetric, and then \(k \in \{2, 3, 6\}\) leaders, which cannot be avoided; holes allowed, \(O(n^2)\) rounds as stated.

Assumed (added on the last edge are outlined)

+Memoryconstant memory and local communication+Orientationcommon chirality

Not assumed

Schedulerweak: non-atomic activations, an action may interleave with othersMovementstationary: particles never moveCommunicationlocal: only between neighbouring particlesRandomnessdeterministicInitial shapeconnected, holes allowedConnectivity during executionthe system must stay connected
Formal definitions of this setting
Memory: constant memory
Each particle has \(O(1)\) bits of persistent memory and reads or writes neighbours' memory.
Scheduler: weak scheduler
An activation's look, compute and move need not be atomic; concurrent activations may interfere. The scheduler of Bazzi and Briones is described as weak sequential, as non-atomic, and as fair asynchronous by different later papers Briones et al. 2023 Dufoulon et al. 2021 Chalopin et al. 2026b.
Orientation: chirality
All particles agree on clockwise order, not on a common direction.
Movement: stationary
No particle ever expands or contracts; the configuration is fixed and only states change.
Communication: local communication
A particle exchanges constant-size information only with the particles on adjacent nodes, by messages or by reading and writing their memory, so information travels at most one particle per activation.
Randomness: deterministic
No random choices.
Initial shape: holes allowed
The initial set of occupied nodes induces a connected subgraph; it may enclose empty regions.
Connectivity during execution: stays connected
At every time the occupied nodes induce a connected subgraph.

Statement for this variant

Elect a unique leader when the configuration allows it; otherwise elect \(k\) leaders, where \(k \in \{2, 3, 6\}\) is the symmetricity of the configuration. Holes are allowed.

What is known

Time · asynchronous rounds
unknown
No round lower bound; the \(O(n^2)\) upper bound is stated without proof. A unique leader is impossible on \(k\)-symmetric configurations, so the relaxation to \(k\) leaders is necessary.
lower bound
\(\text{unique leader impossible}\) Bazzi & Briones 2019
bottlenecksymmetry breaking
holds when
  • Section 5.3: deterministic, stationary algorithms
  • a configuration with \(k\)-fold rotational symmetry, \(k \in \{2, 3, 6\}\): fewer than \(k\) leaders cannot be elected
  • weak scheduler: all particles read their neighbours' memory, then all write, and the cycle repeats
  • holds even with chirality
With a strong scheduler symmetry can be broken without moving, for example between two particles (Section 6).
introductory—
current best
\(O(n^2)\)
Moves · total expansions and contractions (work)
tight
No moves.
lower boundnone known
introductory—
current best—

Results, in order of publication

Bazzi & Briones 2019 current best
Time \(O(n^2)\)

Introductory and current best: a unique leader whenever the configuration is not \(k\)-symmetric, otherwise exactly \(k\) leaders (Sections 4–6). First 1, 2, 3 or 6 candidates are elected on the outer boundary by merging stretches (runs of consecutive points along the boundary, each carrying the sum of the \(\pm 1\) labels of its points, at most 6), then candidates grow trees and compare them. The \(O(n^2)\) bound is stated in the abstract (as steps) and in Table 1 (as rounds); the paper gives no proof of it.

Open questions

  1. Prove, or improve, the \(O(n^2)\)-round bound of Bazzi & Briones 2019, which the paper states without proof, and give a lower bound on rounds.

  2. Elect a bounded number of leaders deterministically, without moving, under the weak scheduler and without chirality, on configurations with holes; Bazzi and Briones conjecture that it is possible Bazzi & Briones 2019.

Notes

Model (Section 2): anonymous particles with finite memory and chirality, all contracted, connected, holes allowed; a particle reads its neighbours' memory and writes its own, but not in one atomic step, and the scheduler may activate a particle any finite number of times before another. The question whether a unique leader is ever impossible here (raised from Dufoulon et al. 2021) is answered by Section 5.3 of Bazzi & Briones 2019: yes, on every \(k\)-symmetric configuration with \(k \in \{2, 3, 6\}\). Bazzi and Briones report that Emek et al. 2019 use their algorithm, announced at SSS 2018, as a subroutine. Checked against the full text.

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.

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