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›oblivious, weak scheduler, no orientation, + may move

SILBOT with holes

verified
Time: impossibleMoves: unknown

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.

Assumed (added on the last edge are outlined)

+Movementparticles may move

Not assumed

Memoryoblivious, silent particles (SILBOT)Schedulerweak: non-atomic activations, an action may interleave with othersOrientationno common orientation and no chiralityRandomnessdeterministicInitial shapeconnected, holes allowedConnectivity during executionthe system must stay connected
Formal definitions of this setting
Memory: oblivious
No persistent state and no messages; a particle decides from its view only.
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: may move
Particles may expand and contract during the election.
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

Particle leader election as in the hole-free SILBOT variant (one, two or three mutually adjacent leaders), from any connected configuration of contracted particles, possibly with holes, keeping the system connected.

What is known

Time · asynchronous rounds
impossible
Impossible in plain SILBOT; with exterior awareness \(O(n^2)\) rounds and no lower bound.
lower bound
\(\text{impossible}\) D'Angelo et al. 2020
bottlenecksymmetry breaking
holds when
  • a connected configuration with a hole in which groups of particles have identical 2-hop views
  • the adversary activates each such set simultaneously, each particle twice in a row
  • the system must stay connected
  • holds even with unlimited memory and chirality
Theorem 2: every move some particle could be instructed to make disconnects the system under some schedule.
introductory—
current best
\(O(n^2)\)
exterior awareness: a particle tells an empty node in a hole from an exterior empty node within its view2-hop view
Moves · total expansions and contractions (work)
unknown
Not analysed.
lower boundnone known
introductory—
current best—

Results, in order of publication

D'Angelo et al. 2020 current best
Time \(O(n^2)\)
exterior awareness: a particle tells an empty node in a hole from an exterior empty node within its view2-hop view

Introductory and current best: Algorithm CHLE (Theorem 3) fills the holes (compaction: the configuration becomes simply connected) while electing at most three leaders; on hole-free configurations it behaves as LESC.

Open questions

  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.

Notes

Compaction (of holes) asks to turn any connected configuration into a simply connected one. Exterior awareness is motivated by local sensing (light or pressure). Checked against the full text of D'Angelo et al. 2020.

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.

Branches from here

Silent oblivious particles (SILBOT)

+no holes
Silent oblivious particles (SILBOT) elect at most three mutually adjacent leaders from hole-free configurations in \(O(n)\) rounds.

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