Polylogarithmic time algorithms for shortest path forests in programmable matter - Padalkin, Andreas; Scheideler, Christian (Distributed Computing)
Abstract In this paper, we study the computation of shortest paths within the geometric amoebot model , a commonly used model for programmable matter. Shortest paths are essential for various tasks and therefore have been heavily investigated in many different contexts. We consider the reconfigurable circuit extension of the model where the amoebot structure is able to interconnect amoebots by so-called circuits. These circuits permit the instantaneous transmission of simple signals between connected amoebots. We propose distributed algorithms for the shortest path forest problem where, given a set of k sources and a set of $$\ell $$ ℓ destinations, the amoebot structure has to compute a forest that connects each destination to its closest source on a shortest path. Our main results are two algorithms for hole-free structures. The first algorithm constructs a shortest path tree for a single source within $$O(\log \ell )$$ O ( log ℓ ) rounds, and the second algorithm a shortest path forest for an arbitrary number of sources within $$O(\log n \log ^2 k)$$ O ( log n log 2 k ) rounds. The former algorithm also provides an O (1) rounds solution for the single pair shortest path problem (SPSP) and an $$O(\log n)$$ O ( log n ) rounds solution for the single source shortest path problem (SSSP) since these problems are special cases of the considered problem. Then, we adapt the latter algorithm to an offset version of the problem. This allows us to solve the problem for amoebot structures with holes within $$O(h \log ^3 n)$$ O ( h log 3 n ) rounds w.h.p. where h denotes the number of holes.

Fast Distributed Computation of Compact Routing Schemes - Dou, Jinfeng; Götte, Thorsten; Hillebrandt, Henning; Scheideler, Christian; Werthmann, Julian (Lecture Notes in Computer Science)

Supervised Distributed Computing: Efficiency and Robustness under a Majority of Adversarial Workers - Augustine, John; Hillebrandt, Henning; Kumar, Manish; Scheideler, Christian; Werthmann, Julian (Proceedings of the ACM Symposium on Principles of Distributed Computing)

Distributed rhombus formation of sliding squares - Kostitsyna, Irina; Liedtke, David; Scheideler, Christian (Theoretical Computer Science)
The sliding square model is a widely used abstraction for studying self-reconfigurable robotic systems, where modules are square-shaped robots that move by sliding or rotating over one another. In this paper, we propose a novel distributed algorithm that enables a group of modules to reconfigure into a rhombus shape, starting from an arbitrary side-connected configuration. It is connectivity-preserving and operates under minimal assumptions: one leader module, common chirality, constant memory per module, and visibility and communication restricted to immediate neighbors. Unlike prior work, which relaxes the original sliding square move-set, our approach uses the unmodified move-set, addressing the additional challenge of handling locked configurations. Our algorithm is sequential in nature and operates with a worst-case time complexity of O(n^2) rounds, which is optimal for sequential algorithms. To improve runtime, we introduce two parallel variants of the algorithm. Both rely on a spanning tree data structure, allowing modules to make decisions based on local connectivity. Our experimental results show a significant speedup for the first variant, and a linear average runtime for the second variant, which is worst-case optimal for parallel algorithms.
Keywords: modular robots; distributed algorithms; sliding squares

Invited Paper: Distributed Rhombus Formation of Sliding Squares - Kostitsyna, Irina; Liedtke, David Jan; Scheideler, Christian (Stabilization, Safety, and Security of Distributed Systems)
The sliding square model is a widely used abstraction for studying self-reconfigurable robotic systems, where modules are square-shaped robots that move by sliding or rotating over one another. In this paper, we propose a novel distributed algorithm that enables a group of modules to reconfigure into a rhombus shape, starting from an arbitrary side-connected configuration. It is connectivity-preserving and operates under minimal assumptions: one leader module, common chirality, constant memory per module, and visibility and communication restricted to immediate neighbors. Unlike prior work, which relaxes the original sliding square move-set, our approach uses the unmodified move-set, addressing the additional challenge of handling locked configurations. Our algorithm is sequential in nature and operates with a worst-case time complexity of O(n^2) rounds, which is optimal for sequential algorithms. To improve runtime, we introduce two parallel variants of the algorithm. Both rely on a spanning tree data structure, allowing modules to make decisions based on local connectivity. Our experimental results show a significant speedup for the first variant, and a linear average runtime for the second variant, which is worst-case optimal for parallel algorithms.

Reconfiguration and locomotion with joint movements in the amoebot model. Auton. Robots 49(3): 22 (2025) - Scheideler, Christian; Padalkin, Andreas; Kumar, Manish (Reconfiguration and locomotion with joint movements in the amoebot model. Auton. Robots 49(3): 22 (2025))

AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). - Scheideler, Christian; Artmann, Matthias; Maurer, Tobias; Padalkin, Andreas; Warner, Daniel

4th Symposium on Algorithmic Foundations of Dynamic Networks.

On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. - Scheideler, Christian; Artmann, Matthias; Padalkin, Andreas

Supervised Distributed Computing. - Scheideler, Christian; Augustine , John; Werthmann, Julian

Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs - Dou, Jinfeng; Götte, Thorsten; Hillebrandt, Henning; Scheideler, Christian; Werthmann, Julian (16th Innovations in Theoretical Computer Science Conference (ITCS 2025))

Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures - Hinnenthal, Kristian; Liedtke, David Jan; Scheideler, Christian (Theoretical Computer Science)

Supervised Distributed Computing - Augustine, John; Scheideler, Christian; Werthmann, Julian (Lecture Notes in Computer Science)

Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures - Hinnenthal, Kristian; Liedtke, David Jan; Scheideler, Christian (3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024))
This paper considers the shape formation problem within the 3D hybrid model, where a single agent with a strictly limited viewing range and the computational capacity of a deterministic finite automaton manipulates passive tiles through pick-up, movement, and placement actions. The goal is to reconfigure a set of tiles into a specific shape termed an icicle. The icicle, identified as a dense, hole-free structure, is strategically chosen to function as an intermediate shape for more intricate shape formation tasks. It is designed for easy exploration by a finite state agent, enabling the identification of tiles that can be lifted without breaking connectivity. Compared to the line shape, the icicle presents distinct advantages, including a reduced diameter and the presence of multiple removable tiles. We propose an algorithm that transforms an arbitrary initially connected tile structure into an icicle in 𝒪(n³) steps, matching the runtime of the line formation algorithm from prior work. Our theoretical contribution is accompanied by an extensive experimental analysis, indicating that our algorithm decreases the diameter of tile structures on average.
Keywords: Programmable Matter; Shape Formation; 3D Model; Finite Automaton

Universal Coating by 3D Hybrid Programmable Matter - Kostitsyna, Irina; Liedtke, David Jan; Scheideler, Christian (Structural Information and Communication Complexity)
Motivated by the prospect of nano-robots that assist human physiological functions at the nanoscale, we investigate the coating problem in the three-dimensional model for hybrid programmable matter. In this model, a single agent with strictly limited viewing range and the computational capability of a deterministic finite automaton can act on passive tiles by picking up a tile, moving, and placing it at some spot. The goal of the coating problem is to fill each node of some surface graph of size n with a tile. We first solve the problem on a restricted class of graphs with a single tile type, and then use constantly many tile types to encode this graph in certain surface graphs capturing the surface of 3D objects. Our algorithm requires O(n^2) steps, which is worst-case optimal compared to an agent with global knowledge and no memory restrictions.
Keywords: Programmable Matter; Coating; Finite Automaton; 3D

The structural power of reconfigurable circuits in the amoebot model - Padalkin, Andreas; Scheideler, Christian; Warner, Daniel (Natural Computing)
Abstract The amoebot model (Derakhshandeh et al. in: SPAA ACM, pp 220–222. https://doi.org/10.1145/2612669.2612712 , 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. in J Comput Biol 29(4):317–343. https://doi.org/10.1089/cmb.2021.0363 , 2022) of the geometric 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 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 be used to solve the skeleton problem , where a cycle of amoebots has to be found in the given amoebot structure which contains all boundary amoebots. A canonical solution to that problem can 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 allows 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.

Reconfiguration and Locomotion with Joint Movements in the Amoebot Model - Padalkin, Andreas; Kumar, Manish; Scheideler, Christian (3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece)

Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter - Padalkin, Andreas; Scheideler, Christian (Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing)

Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20 - Scheideler, Christian; Hinnenthal , Kristian; Liedtke, David Jan

Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. - Scheideler, Christian; Padalkin, Andreas