Brief Announcement: Leader Election with Noisy Reconfigurable Circuits in the Amoebot Model

We give, to the best of our knowledge, the first leader election algorithm for the Amoebot model with noisy circuit beeps. The algorithm is Las Vegas and terminates in $O(\sqrt{\log n}\log n)$ rounds w.h.p., which is only an $O(\sqrt{\log n})$ factor over the noiseless circuit time bound. In the noiseless circuit model the same algorithm runs in $O(\log n)$ rounds w.h.p. and remains Las Vegas, whereas the previous circuit-based leader election algorithm is Monte Carlo [6]. Beyond leader election, once a leader is elected, our primitives allow any stationary algorithm that is correct in the noiseless circuit model to be simulated in the noisy-circuit model with only an $O(\sqrt{\log n})$ multiplicative overhead. Unlike boundary-erosion approaches, the algorithm is stationary and does not rely on simple connectedness: holes in the amoebot structure are allowed. The formulation is also lattice-generic: it covers the triangular grid and the FCC lattice uniformly, and it is parameterized by the finite symmetry group used for local orientations. Thus it separates the communication problem created by noisy circuits from grid-specific geometric case distinctions.

Classic-model leader election started with the Amoebot model [3, 4]; the best local randomized algorithm elects a leader in $O(n)$ asynchronous rounds w.h.p. using constant memory and no IDs or global coordinates [2]. Deterministic election without circuits uses movement to break symmetries [5] or imposes shape/orientation assumptions. For 3D, Gastineau et al. and Briones et al. study FCC-based/local deterministic variants under additional geometric or scheduler assumptions [7, 1]. In contrast, our circuit-based formulation can use the full FCC octahedral symmetry group $O_h$ of order 48, including orientation-reversing symmetries, rather than only the 24 proper rotations considered in prior FCC leader election work; it also allows 3D systems with holes. Fault-tolerant Amoebot work has mostly focused on crash/recovery-style faults, e.g. shape formation [8]; our faults are transient losses in long-range circuit beeps.

Each amoebot has a local port labeling and an unknown global orientation from a finite lattice symmetry group $𝒢$. Adjacent amoebots can compare relative orientations, written $\sigma (u,v)\in 𝒢$. All procedures below use only constant local memory; whenever an $O(\log n)$-bit coordinate comparison is mentioned, it is generated and compared bit-by-bit by repeated applications of the PASC algorithm rather than stored as a word at a particle.

We use the circuit extension of Feldmann et al. and its subsequent structural primitives [6, 9]. Each amoebot provides a constant number of pins, and in every round it partitions its pins into partition sets. External links connect pins of neighboring amoebots; the connected components of the resulting pin graph are called circuits. A circuit is not a Boolean circuit: it is a dynamically configurable, wire-like communication bus. If an amoebot beeps on one partition set of a circuit in the noiseless model, all partition sets on that circuit receive a beep in the next round. In our noisy model, if at least one amoebot beeps on a circuit $C$ in round $t$, then each amoebot connected to $C$ receives the beep in round $t+1$ independently with probability $1-\epsilon$, where $\epsilon \in (0,1)$ is a fixed constant. Direct neighbor-to-neighbor communication (pin-to-pin) is assumed reliable; this is only for efficiency, since noisy pin-to-pin beeps can be amplified as well, preserving correctness but increasing the leader-election time to $O({\log }^{2}n)$ and the simulation overhead to $O(\log n)$.

With this communication model in place, Theorem 1 states our Las Vegas leader-election result for noisy circuits, while Theorem 2 shows that, once a leader is available, stationary noiseless-circuit algorithms can be simulated in the noisy-circuit model with small overhead.

Assume each amoebot $v$ initially has a private bit $b(v)\in \{0,1\}$. The flooding task is to let all amoebots decide whether ${\bigvee }_{v}b(v)=1$. Whenever an amoebot initially has $b(v)=1$, or hears a circuit beep for the first time, it becomes informed, repeatedly beeps on the circuit, and reliably informs its local neighbors. Repeated circuit beeps quickly create informed “seeds” throughout the structure, and local propagation fills the remaining gaps.

For higher-level protocols, it is not sufficient that all amoebots eventually learn a bit; a reference amoebot must also know when dissemination has completed. We implement an acknowledgment (ACK) primitive on a chain of amoebots with a designated reference amoebot, as is standard in circuit-based constructions. The chain is equipped with a dedicated ACK circuit, initially disconnected. Whenever an amoebot becomes informed, it connects its local ACK pins to the predecessor direction, so the ACK circuit gradually becomes connected from the tail toward the reference amoebot. The tail periodically beeps on the ACK circuit; only once the circuit is fully connected can such a beep reach the reference amoebot, and noisy reception is overcome within $O(\sqrt{\log n})$ rounds w.h.p. by the same segment-hit and local-propagation argument as for flooding.

Attrition alone is not enough for a Las Vegas algorithm: a candidate may stop only after verifying that no other candidate tree remains. For a rooted tree, solitude verification tests whether any edge connects two different trees. First, we compare root-relative orientations: using stored products of relative orientations, adjacent amoebots can test whether their roots have the same global orientation. If not, the two amoebots belong to different trees and the verification aborts. If the root orientations agree, the endpoints compare the two roots’ positions in that common root frame. They do not store $O(\log n)$-bit coordinates; instead, the relevant displacement and edge-offset sums are produced by the PASC algorithm and compared bit by bit. A boundary edge whose two computed root positions differ triggers an abort. If no abort reaches the root, the tree is unique and the root safely declares itself leader. This one-sided check may delay termination but cannot certify two leaders, which proves the Las Vegas safety in Theorem 1. The same bitwise comparison can also be used in a deterministic symmetry-breaking variant to retain canonical maximal roots, although without randomness or movement symmetric configurations can leave several candidates related by the residual lattice symmetries.

The solitude test only needs constant-size lattice data: relative orientations across edges, edge displacements in local frames, and a finite encoding order for $𝒢$. For adjacent amoebots $u,v$, it compares the two descriptions of the same edge after transport to the corresponding root frames. Identical roots make the transported displacements cancel; distinct roots expose, on some tree-boundary edge, either a nonzero displacement or a different root orientation. Holes are therefore not problematic: the algorithm never identifies empty-region boundaries, but only tests whether an occupied edge crosses between candidate trees.

An amoebot keeps only constant-size state: its phase, Euler-tour ports, a root-relative orientation in finite $𝒢$, and flooding/ACK flags. Whenever a coordinate comparison is needed, PASC streams the relevant prefix-sum bits; particles compare the first differing bit and discard it before the next bit is generated. Thus the $O(\log n)$-bit arithmetic used in the analysis is distributed computation, not particle memory.

Safety follows from the one-sided verification: a candidate becomes leader only if every tree-boundary edge has failed to witness a distinct root. Because the tree-adjacency graph is connected whenever more than one tree remains, this can happen only when the candidate tree spans all amoebots. Liveness follows from attrition and the robust primitives. With high probability, all broadcasts and acknowledgments in the first $O(\log n)$ attrition rounds complete within their $O(\sqrt{\log n})$-round windows, and the number of candidates drops to one.