Leader election in programmable matter

Introductory and current best (Theorem 1.1 and Section 1.2.1 of the arXiv version): all particles link their pins into one global circuit. In each step every candidate flips a coin and beeps on the circuit in the first of two rounds if it flipped heads, in the second if tails; if some candidate beeped in the first round, those that beeped in the second drop out. A second tournament run in parallel, repeated a constant number of times, ends the election after \(\Theta(\log n)\) rounds. The scheme adapts the beeping-model election of Gilbert and Newport, as the authors report.

Candidates are roots of trees that merge by coin flips, and a candidate stops only after checking, bit by bit, that no edge joins two trees, so the algorithm never elects two leaders. With noisy circuits, on which each particle hears a beep only with probability \(1-\varepsilon\) for a constant \(\varepsilon \in (0,1)\) while communication between neighbours stays reliable, it takes \(O(\sqrt{\log n}\,\log n)\) rounds with high probability (Theorem 1); once a leader exists, any stationary algorithm for noiseless circuits runs with a factor \(O(\sqrt{\log n})\) of overhead (Theorem 2). It works on the triangular lattice and on the face-centred cubic lattice in three dimensions. A brief announcement.