Leader election in programmable matter: Oblivious, common compass, holes allowed

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, + sequential, + common compass, + may move

Oblivious, common compass, holes allowed

verified

Time: unknownMoves: unknown

Oblivious particles that agree on all directions elect a unique leader in connected configurations with holes, self-stabilising, using movement, under an unfair sequential scheduler.

Assumed (added on the last edge are outlined)

+Schedulersequential: one particle active at a time+Orientationfull common orientation (compass)+Movementparticles may move

Not assumed

Memoryoblivious, silent particles (SILBOT)RandomnessdeterministicInitial 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: sequential: At most one particle is active at any time.
Orientation: common compass: All particles agree on all six directions.
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.

What is known

Time · asynchronous rounds

unknown

—

lower boundnone known

introductory—

current best

\(\text{finite}\)

Chalopin et al. 2026

unfair sequential scheduler with atomic moves

Moves · total expansions and contractions (work)

unknown

—

lower boundnone known

introductory—

current best—

Results, in order of publication

Chalopin et al. 2026 current best

Time \(\text{finite}\)

unfair sequential scheduler with atomic moves

Introductory and current best; silent self-stabilising.

Open questions

None recorded for this variant.

Notes

The abstract says "common sense of direction"; Section 2 assumes agreement on all directions. Movement together with this orientation overcomes the impossibility of constant-memory self-stabilising election in general networks Chalopin et al. 2026. 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

SILBOT with holes

Time \(O(n^2)\)

Lower bounds from stronger settings hold here

No catalogued stronger setting.

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