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›+ strong scheduler›+ common direction

Stationary, common direction, no chirality

verified
Time: unknownMoves: tight

With one common direction and no chirality, a unique leader is elected without moving, with obstacles allowed, but only with implicit termination.

Assumed (added on the last edge are outlined)

+Memoryconstant memory and local communication+Schedulerstrong: atomic activations under a fair adversary+Orientationa common direction, no chirality

Not assumed

Movementstationary: 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: strong scheduler
Each activation is executed atomically; the adversary chooses the order, fairly.
Orientation: common direction
All particles agree on one lattice direction, not on handedness. Chalopin, Das and Kokkou call this a common direction Chalopin et al. 2026, but the same words mean agreement on all six directions in other papers Chalopin et al. 2026 Navarra & Piselli 2023.
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.

What is known

Time · asynchronous rounds
unknown
No round bound recorded.
lower bound
\(\text{explicit termination impossible}\) Chalopin et al. 2026
bottlenecksymmetry breaking
holds when
  • Theorem 1: deterministic algorithms
  • connected configuration with obstacles (holes)
  • common direction (one axis), no chirality
  • holds even under a synchronous scheduler
  • implicit termination remains possible
introductory—
current best
\(O(n^3)\)
Moves · total expansions and contractions (work)
tight
No moves.
lower boundnone known
introductory—
current best—

Results, in order of publication

Chalopin et al. 2026 current best
Time \(O(n^3)\)

Introductory and current best (Section 6); implicit termination, unique leader, deterministic, stationary.

Open questions

None recorded for this variant.

Notes

With chirality but no common direction, explicit termination is always possible but the number of leaders depends on the symmetry of the initial configuration Chalopin et al. 2026. Here "common direction" means agreement on one axis only. Checked against the full text.

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