2026-09-08T02:22:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26259 2026-09-05T19:39:53Z ddc:004 open_access

Brief Announcement: Fault-Tolerant 3D Leader Election in the Amoebot Model Warner, Daniel Scheideler, Christian Programmable matter amoebot model leader election fault tolerance 3D lattices symmetry groups We study leader election for programmable matter in the amoebot model when particles operate on a lattice graph and may experience crash-recovery failures. We propose a lattice-group view that captures both the classical 2D triangular grid and the 3D face-centered cubic (FCC) grid, including configurations with holes and the full lattice symmetry group. To the best of our knowledge, this is the first leader-election framework for 3D amoebot systems that simultaneously handles holes, the full lattice symmetry group including reflections, and crash-recovery faults. We outline (i) a randomized fault-tolerant leader election algorithm based on Borůvka-style merging of candidate-rooted trees combined with a coordinate-based solitude-verification, and (ii) a deterministic approach for assorted local orientations that simulates a virtual instance for each possible orientation in the symmetry group and breaks residual symmetries via a centroid-guided movement phase. Logarithmic-size coordinates are streamed or stored distributively, preserving constant local memory, while crashes are handled by rerooting so failures partition trees without destroying the global competition structure. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Warner and Christian Scheideler 2026 Is Part Of LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2026.25 urn:nbn:de:0030-drops-262593 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.25 eng https://creativecommons.org/licenses/by/4.0/legalcode