Search Results

Documents authored by Warner, Daniel

Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2026.25
Brief Announcement: Fault-Tolerant 3D Leader Election in the Amoebot Model

Authors: Daniel Warner and Christian Scheideler

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract
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.
Cite as

Daniel Warner and Christian Scheideler. Brief Announcement: Fault-Tolerant 3D Leader Election in the Amoebot Model. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 25:1-25:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{warner_et_al:LIPIcs.SAND.2026.25,
  author =	{Warner, Daniel and Scheideler, Christian},
  title =	{{Brief Announcement: Fault-Tolerant 3D Leader Election in the Amoebot Model}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{25:1--25:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.25},
  URN =		{urn:nbn:de:0030-drops-262593},
  doi =		{10.4230/LIPIcs.SAND.2026.25},
  annote =	{Keywords: Programmable matter, amoebot model, leader election, fault tolerance, 3D lattices, symmetry groups}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2026.26
Brief Announcement: Leader Election with Noisy Reconfigurable Circuits in the Amoebot Model

Authors: Daniel Warner and Christian Scheideler

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract
Reconfigurable circuits substantially accelerate coordination tasks in the geometric Amoebot model, but existing circuit-based leader election assumes perfectly reliable circuit beeps and provides only Monte Carlo guarantees. We introduce a natural fault model in which circuit beeps are noisy: whenever at least one amoebot beeps on a circuit in a round, each amoebot hears that beep in the next round independently with probability 1-ε, while direct neighbor-to-neighbor (pin-to-pin) communication remains reliable. In this noisy-circuit model we give a Las Vegas leader election algorithm that terminates in O(√{log n} log n) rounds w.h.p. Moreover, once a leader is elected, we show how to simulate any stationary algorithm that is correct in the noiseless circuit model with only an O(√{log n}) multiplicative overhead in running time. Our techniques combine robust flooding/acknowledgment primitives with a tree-based competition framework (Euler-tour representation, randomized attrition, and deterministic solitude verification).
Cite as

Daniel Warner and Christian Scheideler. Brief Announcement: Leader Election with Noisy Reconfigurable Circuits in the Amoebot Model. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 26:1-26:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{warner_et_al:LIPIcs.SAND.2026.26,
  author =	{Warner, Daniel and Scheideler, Christian},
  title =	{{Brief Announcement: Leader Election with Noisy Reconfigurable Circuits in the Amoebot Model}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{26:1--26:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.26},
  URN =		{urn:nbn:de:0030-drops-262606},
  doi =		{10.4230/LIPIcs.SAND.2026.26},
  annote =	{Keywords: Programmable matter, amoebot model, leader election, reconfigurable circuits, noisy beeps, Las Vegas algorithms}
}
Artifact
Software
DOI: 10.4230/artifacts.23289
AmoebotSim 2.0

Authors: Matthias Artmann, Tobias Maurer, Andreas Padalkin, Daniel Warner, and Christian Scheideler

Abstract
Cite as

Matthias Artmann, Tobias Maurer, Andreas Padalkin, Daniel Warner, Christian Scheideler. AmoebotSim 2.0 (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23289,
   title = {{AmoebotSim 2.0}}, 
   author = {Artmann, Matthias and Maurer, Tobias and Padalkin, Andreas and Warner, Daniel and Scheideler, Christian},
   note = {Software, version 1.8.4., DFG-SCHE 1592/10-1, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:41a83f85a3e7c6c1d5a2fec79533bef04c7ff770;origin=https://github.com/martmannupb/AmoebotSim-2.0;visit=swh:1:snp:8aeb8f3c490d90e04facd9ff0fd699c06b8a2ab6;anchor=swh:1:rev:5873cfc9aa08099e3ebf3b0ce334b8f28cbda75f}{\texttt{swh:1:dir:41a83f85a3e7c6c1d5a2fec79533bef04c7ff770}} (visited on 2025-06-20)},
   url = {https://github.com/martmannupb/AmoebotSim-2.0},
   doi = {10.4230/artifacts.23289},
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2025.81
AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition)

Authors: Matthias Artmann, Tobias Maurer, Andreas Padalkin, Daniel Warner, and Christian Scheideler

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present AmoebotSim 2.0, a simulation environment for the geometric amoebot model of programmable matter that supports the reconfigurable circuit and joint movement extensions of the model. In the geometric amoebot model, we consider systems of simple computational entities called amoebots in a regular triangular grid environment. We are interested in distributed algorithms that solve coordination and shape formation problems. The reconfigurable circuit and joint movement extensions of the model allow the amoebots to communicate over greater distances and perform more complex movements, overcoming some limitations of the original model. AmoebotSim 2.0 is an open-source simulation environment that supports these extensions and provides a rich graphical interface, flexible simulation features, an extensive API, and comprehensive documentation.
Cite as

Matthias Artmann, Tobias Maurer, Andreas Padalkin, Daniel Warner, and Christian Scheideler. AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 81:1-81:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{artmann_et_al:LIPIcs.SoCG.2025.81,
  author =	{Artmann, Matthias and Maurer, Tobias and Padalkin, Andreas and Warner, Daniel and Scheideler, Christian},
  title =	{{AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{81:1--81:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.81},
  URN =		{urn:nbn:de:0030-drops-232338},
  doi =		{10.4230/LIPIcs.SoCG.2025.81},
  annote =	{Keywords: Programmable matter, amoebot model, reconfigurable circuits, joint movements, simulator}
}
Document
DOI: 10.4230/LIPIcs.DNA.28.8
The Structural Power of Reconfigurable Circuits in the Amoebot Model

Authors: Andreas Padalkin, Christian Scheideler, and Daniel Warner

Published in: LIPIcs, Volume 238, 28th International Conference on DNA Computing and Molecular Programming (DNA 28) (2022)

Abstract
The amoebot model [Derakhshandeh et al., SPAA 2014] has been proposed as a model for programmable matter consisting of tiny, robotic elements called amoebots. We consider the reconfigurable circuit extension [Feldmann et al., JCB 2022] of the geometric (variant of the) amoebot model that allows the amoebot structure to interconnect amoebots by so-called circuits. A circuit permits the instantaneous transmission of signals between the connected amoebots. In this paper, we examine the structural power of the reconfigurable circuits. We start with some fundamental problems like the stripe computation problem where, given any connected amoebot structure S, an amoebot u in S, and some axis X, all amoebots belonging to axis X through u have to be identified. Second, we consider the global maximum problem, which identifies an amoebot at the highest possible position with respect to some direction in some given amoebot (sub)structure. A solution to this problem can then be used to solve the skeleton problem, where a (not necessarily simple) cycle of amoebots has to be found in the given amoebot structure which contains all boundary amoebots. A canonical solution to that problem can then be used to come up with a canonical path, which provides a unique characterization of the shape of the given amoebot structure. Constructing canonical paths for different directions will then allow the amoebots to set up a spanning tree and to check symmetry properties of the given amoebot structure. The problems are important for a number of applications like rapid shape transformation, energy dissemination, and structural monitoring. Interestingly, the reconfigurable circuit extension allows polylogarithmic-time solutions to all of these problems.
Cite as

Andreas Padalkin, Christian Scheideler, and Daniel Warner. The Structural Power of Reconfigurable Circuits in the Amoebot Model. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{padalkin_et_al:LIPIcs.DNA.28.8,
  author =	{Padalkin, Andreas and Scheideler, Christian and Warner, Daniel},
  title =	{{The Structural Power of Reconfigurable Circuits in the Amoebot Model}},
  booktitle =	{28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
  pages =	{8:1--8:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-253-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{238},
  editor =	{Ouldridge, Thomas E. and Wickham, Shelley F. J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.28.8},
  URN =		{urn:nbn:de:0030-drops-167935},
  doi =		{10.4230/LIPIcs.DNA.28.8},
  annote =	{Keywords: progammable matter, amoebot model, reconfigurable circuits, spanning tree, symmetry detection}
}
Document
DOI: 10.4230/LIPIcs.DNA.28.9
Fault-Tolerant Shape Formation in the Amoebot Model

Authors: Irina Kostitsyna, Christian Scheideler, and Daniel Warner

Published in: LIPIcs, Volume 238, 28th International Conference on DNA Computing and Molecular Programming (DNA 28) (2022)

Abstract
The amoebot model is a distributed computing model of programmable matter. It envisions programmable matter as a collection of computational units called amoebots or particles that utilize local interactions to achieve tasks of coordination, movement and conformation. In the geometric amoebot model the particles operate on a hexagonal tessellation of the plane. Within this model, numerous problems such as leader election, shape formation or object coating have been studied. One area that has not received much attention so far, but is highly relevant for a practical implementation of programmable matter, is fault tolerance. The existing literature on that aspect allows particles to crash but assumes that crashed particles do not recover. We proposed a new model [Kostitsyna et al., 2022] in which a crash causes the memory of a particle to be reset and a crashed particle can detect that it has crashed and try to recover using its local information and communication capabilities. We present an algorithm that solves the hexagon shape formation problem in our model if a finite number of crashes occur and a designated leader particle does not fail. At the heart of our solution lies a fault-tolerant implementation of the spanning forest primitive, which, since other algorithms in the amoebot model also make use of it, is also of general interest.
Cite as

Irina Kostitsyna, Christian Scheideler, and Daniel Warner. Fault-Tolerant Shape Formation in the Amoebot Model. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.DNA.28.9,
  author =	{Kostitsyna, Irina and Scheideler, Christian and Warner, Daniel},
  title =	{{Fault-Tolerant Shape Formation in the Amoebot Model}},
  booktitle =	{28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-253-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{238},
  editor =	{Ouldridge, Thomas E. and Wickham, Shelley F. J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.28.9},
  URN =		{urn:nbn:de:0030-drops-167949},
  doi =		{10.4230/LIPIcs.DNA.28.9},
  annote =	{Keywords: programmable matter, amoebot model, fault tolerance, shape formation}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2022.23
Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model

Authors: Irina Kostitsyna, Christian Scheideler, and Daniel Warner

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
The amoebot model is a distributed computing model of programmable matter. It envisions programmable matter as a collection of computational units called amoebots or particles that utilize local interactions to achieve tasks of coordination, movement and conformation. In the geometric amoebot model the particles operate on a hexagonal tessellation of the plane. Within this model, numerous problems such as leader election, shape formation or object coating have been studied. One area that has not received much attention so far, but is highly relevant for a practical implementation of programmable matter, is fault tolerance. The existing literature on that aspect allows particles to crash but assumes that crashed particles do not recover. We propose a new model in which a crash causes the memory of a particle to be reset and a crashed particle can detect that it has crashed and try to recover using its local information and communication capabilities. We propose an algorithm that solves the hexagon shape formation problem in our model if a finite number of crashes occur and a designated leader particle does not fail. At the heart of our solution lies a fault-tolerant implementation of the spanning forest primitive, which, since other algorithms in the amoebot model also make use of it, is also of general interest.
Cite as

Irina Kostitsyna, Christian Scheideler, and Daniel Warner. Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 23:1-23:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SAND.2022.23,
  author =	{Kostitsyna, Irina and Scheideler, Christian and Warner, Daniel},
  title =	{{Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{23:1--23:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.23},
  URN =		{urn:nbn:de:0030-drops-159656},
  doi =		{10.4230/LIPIcs.SAND.2022.23},
  annote =	{Keywords: Programmable matter, Geometric amoebot model, Fault tolerance, Shape formation}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact