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).
Silent oblivious particles (SILBOT)
verifiedSilent oblivious particles (SILBOT) elect at most three mutually adjacent leaders from hole-free configurations in \(O(n)\) rounds.
Assumed (added on the last edge are outlined)
Not assumed
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: 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.
Statement for this variant
Particle leader election (PLE): from a connected configuration of contracted particles, terminate with one, two or three mutually adjacent contracted particles that recognise themselves as LEADER, every other particle expanded (NON-LEADER), and the system connected throughout. A single leader is not required: D'Angelo et al. note that a single particle can be elected only with randomisation or a sequential scheduler, citing Emek et al. 2019.
What is known
Results, in order of publication
Introductory and current best: Algorithm LESC (Theorem 1), which only expands particles; an emulation of the erosion of Di Luna et al. 2020 with simpler rules.
Open questions
None recorded for this variant.
Notes
SILBOT D'Angelo et al. 2020 removes from the amoebot model the serialised scheduler (no two neighbouring particles active together), explicit communication, atomicity of actions and randomness. Particles see up to two hops, distinguish empty nodes from contracted and expanded particles, and act asynchronously; a particle that has expanded along an edge is committed and contracts into the target node at its next activation if the node is empty. A round is the shortest period in which every particle has completed an activation. The paper argues that 1-hop visibility is not enough without communication. Holes are handled in the variant without the hole-free assumption. Checked against the full text of D'Angelo et al. 2020 (IEEE Access version; preliminary version at AAMAS 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
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.