Brief Announcement: Fault-Tolerant 3D Leader Election in the Amoebot Model

Each particle $p$ has a private local frame, which we call its orientation; its relation to a global reference frame is represented by an element $\sigma (p)\in G$. Particles do not know $\sigma (p)$, and in an assorted system different particles may have different orientations. We assume two local capabilities:

1. (i)

   For each port, a particle knows the corresponding direction vector in its local coordinates.

2. (ii)

   For adjacent particles $p$ and $q$, each can compute the relative orientation $\rho (p,q)=\sigma {(p)}^{-1}\sigma (q)\in G$, i.e., the group element mapping $p$’s frame to $q$’s frame.

Thus directional and coordinate information can be translated across an edge without a shared compass: if $p$ sends a direction expressed in $p$’s local frame, $q$ can reinterpret it in its own frame by applying $\rho (p,q)$. Whenever an $𝒪(\log n)$-bit coordinate, count, or sum is used below, it is represented as a stream or distributed over $𝒪(\log n)$ particles; no particle stores more than a constant number of bits.

The core invariant is that a crashed particle becomes a root upon recovery. Intuitively, this turns a crash into a controlled cut: the tree containing the crash is partitioned into smaller rooted trees, and all of them continue the leader competition. This follows the principle underlying fault-tolerant shape formation [9]. Two design choices matter here: (i) parent/child relations are stored by the particles incident to a tree edge and can be checked and repaired locally after a crash, and (ii) progress is measured in terms of candidate roots, so crash-induced partitions may delay termination but do not invalidate correctness.

For each rooted tree, particles repeatedly compute their root-relative coordinates in the root’s frame by a distributed prefix-sum procedure over the tree. The computation is performed bit by bit over $𝒪(\log n)$ phases. Adjacent particles then compare their translated coordinates and the lattice edge between them. If the coordinates or root orientations are inconsistent, the edge crosses a tree boundary; if no particle observes such an edge, connectedness implies that the forest consists of a single tree and its root is the unique candidate. The same comparison primitive is used below to order neighboring roots deterministically.

Assume all particles share a common orientation. The solitude verification computation then gives each particle a bitwise representation of its position in a common coordinate system. When two adjacent particles belong to different trees, they bit by bit compare the bitwise coordinate encodings obtained from the solitude-verification computation, after accounting for the offset of their common edge, and identify the first differing bit; in effect, this compares the two roots in the common coordinate system. This boundary comparison decides which root is lexicographically larger and directs the merge toward that root.

In one phase, each tree determines the maximum root coordinate among its neighboring trees and merges to that maximum, unless solitude verification already certifies that it is alone. The boundary-comparison primitive can be pipelined with the prefix-sum computation, so the stationary attrition layer uses $𝒪(\log n)$ merge phases and $𝒪(\log n)$ coordinate-bit phases per merge phase. With $𝒪(n)$ activations per bit phase, the stationary attrition and solitude verification layer finishes after $𝒪(n{\log }^{2}n)$ rounds after the last crash, before any centroid movement is needed.

In the actual model, particles have assorted unknown orientations. To regain comparability deterministically, we exploit that $G$ is finite. Each particle $p$ conceptually maintains $|G|$ virtual instances, one per hypothetical global alignment $g\in G$. Neighboring particles translate messages between their virtual instances using $\rho (p,q)$ so that, within each virtual layer, computations are consistent as if all particles were aligned according to that layer. Since $|G|$ is a lattice constant, this still costs only constant local memory. Running the deterministic merging procedure in all layers in parallel yields at most $|G|$ candidate roots overall, one per surviving symmetry layer.

This is essentially optimal without movement in the presence of symmetries: there exist stationary configurations whose symmetry cannot be broken deterministically by local computation alone. Therefore, if more than one candidate remains, we add a final movement phase that breaks symmetry geometrically.

Each candidate tree aggregates coordinate information, such as sums of position vectors and the node count, to compute a centroid point. The sums and counts are again streamed or stored distributively. Although coordinates are expressed in local frames, relative orientations allow consistent translation of these aggregates. Thus, the centroid computed in different candidate trees refers to the same global point; when expressed back in each tree’s local coordinates, the target is consistent. On the triangular lattice, the centroid may coincide with a lattice point, lie on an edge, or fall inside a face; analogous discretization cases exist in FCC. Once the centroid is reached, or, if it is not a lattice node, once the lattice nodes surrounding it are occupied in the required pattern, the sequential scheduler deterministically breaks the remaining tie among the particles at these positions.

• $\mathrm{■}$

  Option 1 (connectivity-preserving, fault-tolerant): Candidates coordinate moves that monotonically reduce distance to the centroid while preserving global connectivity. This keeps the system coherent and is compatible with crash-recovery faults, at the cost of higher move complexity.

• $\mathrm{■}$

  Option 2 (faster, may disconnect, not fault-tolerant): The system is partitioned into trees rooted at the remaining candidates. These trees are compared by their encodings and merged whenever such a comparison breaks symmetry. Only symmetric trees proceed to the movement phase, where each moves independently toward the computed centroid. This reduces coordination overhead, but independent motion may temporarily disconnect the system; once disconnected, crash recovery is no longer guaranteed.