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

draft
Time: unknownMoves: tight

Without moving, particles with chirality elect at most six leaders in \(O(n^2)\) rounds, holes allowed.

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 moveRandomnessdeterministicInitial 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. 2026.
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.
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

Up to six leaders may be elected.

What is known

Time · asynchronous rounds
unknown
—
lower boundnone known
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; at most six leaders.

Open questions

  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.

Notes

Bounds are from the table of Dufoulon, Kutten and Moses Dufoulon et al. 2021; the abstract of Bazzi & Briones 2019 was not read.

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.