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, no orientation, + no holes

Stationary, asynchronous, no orientation, no holes

verified
Time: unknownMoves: tight

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.

Assumed (added on the last edge are outlined)

+Memoryconstant memory and local communication+Initial shapesimply connected (no holes)

Not assumed

Schedulerweak: non-atomic activations, an action may interleave with othersOrientationno common orientation and no chiralityMovementstationary: particles never moveRandomnessdeterministicConnectivity 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: no orientation
Each particle labels its six incident directions in its own clockwise or counter-clockwise order, starting anywhere.
Movement: stationary
No particle ever expands or contracts; the configuration is fixed and only states change.
Randomness: deterministic
No random choices.
Initial shape: no holes
The initial configuration is connected and encloses no empty node. Also called contractible Briones et al. 2023 or hole-free Gastineau et al. 2019.
Connectivity during execution: stays connected
At every time the occupied nodes induce a connected subgraph.

What is known

Time · asynchronous rounds
unknown
Runtime not analysed under the asynchronous adversary.
lower boundnone known
introductory—
current best
\(\text{finite}\)
Moves · total expansions and contractions (work)
tight
No moves.
lower boundnone known
introductory—
current best—

Results, in order of publication

Briones et al. 2023 current best
Time \(\text{finite}\)

Introductory and current best (Corollary 6): the sequential algorithm transformed by the concurrency control framework Daymude et al. 2023; the paper says its runtime "has not yet been analyzed".

Open questions

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

Notes

Contractible means no holes, in 2D or in 3D (face-centred cubic lattice). Particles have "assorted orientations": no common direction and no chirality. 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.

Lower bounds from stronger settings hold here

Stationary, fair scheduler, no orientation, no holes

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