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).
Stationary, randomized, sequential, holes allowed
draftWith coin flips and a sequential scheduler, stationary particles without a common orientation elect a unique leader, holes allowed, in \(O(n\log n)\) rounds with high probability, as stated without proof in a brief announcement that also tolerates crash-recovery faults.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Memory: constant memory
- Each particle has \(O(1)\) bits of persistent memory and reads or writes neighbours' memory.
- Scheduler: sequential
- At most one particle is active at any time.
- 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.
- Communication: local communication
- A particle exchanges constant-size information only with the particles on adjacent nodes, by messages or by reading and writing their memory, so information travels at most one particle per activation.
- 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
Results, in order of publication
Introductory and current best, as stated in Section 3.2 without proof (a brief announcement). Every candidate is the root of a tree. In each phase every root flips a coin, and a tree whose root flipped 0 attaches to a neighbouring tree whose root flipped 1, so a constant fraction of the candidates disappears in expectation and \(O(\log n)\) phases suffice with high probability. A solitude check certifies that one tree remains: particles compute their coordinates relative to their root bit by bit and compare them across each edge. The paper says "runtime" without naming the unit.
Open questions
Prove the \(O(n\log n)\) bound with high probability that Warner & Scheideler 2026a states without proof, and give a lower bound on rounds.
Can stationary randomized particles without a common orientation elect a unique leader on configurations with holes under the strong or the weak scheduler, which let several particles act at the same time?
Notes
Warner and Scheideler describe the local frame of a particle by a symmetry of the lattice: one of the 12 rotations and reflections of the triangular lattice, or one of the 48 of the face-centred cubic lattice in 3D. A particle does not know its own frame, but two neighbours know how their frames relate. Numbers of \(O(\log n)\) bits are streamed or spread over \(O(\log n)\) particles, so memory stays constant. Faults follow a crash-recovery model from earlier work of Kostitsyna, Scheideler and Warner (DNA 28, 2022; not in this atlas): a crashed particle loses its memory and enters a crashed state that it can detect, and on recovery it becomes the root of its own tree, so a crash cuts a tree into smaller trees that keep competing; correctness is required whenever there are finitely many crashes. The randomized algorithm, as outlined, never moves particles. The same paper outlines a deterministic algorithm: run the stationary merging once for every possible global frame, which leaves at most 12 candidates on the triangular lattice in \(O(n\log^2 n)\) rounds after the last crash, then move the candidates towards the centroid of the configuration until one remains. No bound is given for this movement phase, and its faster option may disconnect the configuration and then loses fault tolerance. Without faults, on the triangular lattice, deterministic election with movement and no orientation is known under the strong scheduler Emek et al. 2019, a weaker assumption than the sequential one. Checked against the full text, a brief announcement without theorems or proofs; the bounds are the authors' statements.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.