Leader election in programmable matter: Randomized, with chirality

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›+ chirality›+ may move›+ randomized

Randomized, with chirality

verified

Time: unknownMoves: unknown

Randomized leader election in a linear number of rounds with high probability.

Assumed (added on the last edge are outlined)

+Memoryconstant memory and local communication+Schedulerstrong: atomic activations under a fair adversary+Orientationcommon chirality+Movementparticles may move+Randomnessrandomized

Not assumed

Initial 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: chirality: All particles agree on clockwise order, not on a common direction.
Movement: may move: Particles may expand and contract during the election.
Randomness: randomized: Particles flip fair coins; guarantees hold with high probability or in expectation.
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 proven lower bound.

lower boundnone known

introductory

\(O(L_{max})\)

Derakhshandeh et al. 2015

current best

\(O(n)\)

Daymude et al. 2017

Moves · total expansions and contractions (work)

unknown

—

lower boundnone known

introductory—

current best—

Results, in order of publication

Derakhshandeh et al. 2015 introductory

Time \(O(L_{max})\)

Expected rounds; \(L_{max}\) is the longest boundary.

Daymude et al. 2017 current best

Time \(O(n)\)

With high probability; restated as \(O(L_{out}+D)\) by Dufoulon et al. 2021.

Open questions

None recorded for this variant.

Notes

In the general amoebot model on arbitrary graphs leader election is impossible, by reduction to anonymous rings Derakhshandeh et al. 2015.

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

Deterministic, no orientation

Time \(O(L_{out}n^2)\)

Stationary, chirality, weak scheduler

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.