Brief Announcement: Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits
Abstract
In this paper, we study the problem of efficiently reducing geometric shapes into other such shapes in a distributed setting through size-changing operations. We develop distributed algorithms using the reconfigurable circuit model to enable fast node-to-node communication. Let denote the number of nodes and the number of turning points in the initial shape. We show that the system of nodes can reduce itself from any tree to a single node using only shrinking operations in rounds w.h.p. and any tree to its incompressible form in rounds given prior knowledge of the incompressible nodes, or without it, w.h.p. We also give an algorithm to transform any tree to a topologically equivalent tree in rounds w.h.p. using both shrinking and growth operations. On the negative side, we show that one cannot hope for -round transformations for all shapes of turning points.
Keywords and phrases:
growth process, shrinking process, collision avoidance, programmable matterFunding:
Andreas Padalkin: This author was supported by the DFG Project SCHE 1592/10-1.Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Computational geometry ; Theory of computation Distributed computing modelsEditors:
Kitty Meeks and Christian ScheidelerSeries and Publisher:

1 Introduction
A central problem in reconfigurable robotics and related areas is for a set of agents to transform from an initial shape into a target shape, efficiently and without violating structural and other constraints. A large part of work has focused on transformations that guide the system through a sequence of configuration changes without altering its size over time. Other work in algorithmic self-assembly and distributed computing, has studied passive size-changing dynamics whose accumulation leads to structural changes over time. Some authors have recently begun to study transformations that can actively form or deform a configuration by locally controlling the addition or removal of individual agents. These processes are motivated by biological and physical systems, such as embryonic growth in multicellular organisms, and by dynamical systems, such as cellular and self-reproducing automata. They are also related to recent work on algorithmic reconfiguration of graphs and networks [3, 5, 8, 7].
The nubot model of [10] is a decentralized algorithmic framework for autonomous growth and self-assembly at the molecular scale. [2] studied the feasibility and centralized complexity of growing geometric shapes through simple forms of growth operations. These were conditioned to affect specific parts of the shape (e.g., whole columns) and were defined to ensure in advance that no collision can happen. In [1], this was extended to general growth operations, aiming for exponentially fast, centralized transformations that avoid collisions.
Parallel transformation processes can be exponentially fast and are highly dynamic, making it difficult to avoid collisions [6]. It is therefore important to have fast and reliable communication within the system – especially over long distances. [4] proposed the deployment of reconfigurable circuits, which allow to connect subsets of agents. Each agent can send simple signals (beeps) through any connected circuit, which is instantaneously received by all agents connected to the same circuit. Reconfigurable circuits have enabled polylogarithmic-time solutions to problems like shape recognition [4] and spanning tree [9].
In this work, we leverage reconfigurable circuits as a communication model for rapid distributed size-changing transformations. In particular, we study distributed algorithms that must efficiently reduce a given shape into a target shape (sometimes a single node) through a sequence of parallel, collision-free shrinking operations, or by combining shrinking and growth. This also offers a new application domain for reconfigurable circuits, which have primarily been applied to the amoebot model and graph problems.
2 Models and Problems
We study a system composed of computational nodes that initially form a connected shape of size on a two-dimensional square grid. Each node occupies a distinct point of the grid and is a subset of all pairs of nodes that are orthogonally adjacent on the grid. Nodes operate as anonymous (and randomized) finite-state automata, executing actions in discrete synchronous rounds. We assume that all nodes agree on a common compass orientation and chirality.
Nodes communicate via reconfigurable circuits [4]. In this model, each edge in is subdivided into a constant number of links, where is the same for all edges. We assume , which is sufficient and necessary for our results. Each node incident to a link owns one of its endpoints, which are called pins. Each node partitions its pins into disjoint sets, called partition sets. Let denote the set of all partition sets of all nodes. Consider the graph , where two partition sets are adjacent in iff there is a link with one pin in and the other in . In each round, each node can reconfigure its partitioning, and send a beep on any subset of its partition sets. At the beginning of the next round, if a beep occurred on a circuit, then all nodes on that circuit will receive a beep but they will gain no information about its origin or the total number of beeps.
In each round, based on their current state and received signals, nodes can execute either a growth operation – adding a new node – or a shrinking operation – absorbing an adjacent node. We adopt the connectivity model of [1], in which edges form only when new nodes are created.111In the full paper, we also consider a model where edges update dynamically as nodes become adjacent. One or more growth operations applied in parallel to nodes of a shape either cause a collision (i.e., a self-intersection or structural violation) or yield a new shape . Let be a tree and its root. A single growth operation applied on a node toward an adjacent point , results in either () generating a new node at point and connecting it to , or () if is already occupied by a node connected to , generating between and , connecting it to both and , and translating the subtree by one unit away from along the axis parallel to . A shrinking operation is the reverse: a node absorbs an adjacent node . If has no other neighbors, it is removed. Otherwise, inherits all ’s neighbors, each of which is translated one unit toward . Let denote the shape at round . A growth process is a set of growth operations applied in parallel, transforming into , where . A shrinking process is defined analogously.222 In some cases, a sequence of operations may combine both growth and shrinking operations.
The relative position of with respect to is defined by the signs of and . Two trees and are geometrically equivalent iff they have the same turning points and segments (possibly of different lengths), and topologically equivalent iff additionally, their turning points share the same relative positions. A column or row of a shape is a column or row of the grid occupied by nodes of . It is called compressible if it contains no turning points, and incompressible otherwise. Nodes of incompressible columns or rows are called incompressible nodes. A shape is incompressible if all its nodes are incompressible. The incompressible form of , denoted by , is the incompressible shape that is topologically equivalent to .
We study the problem of reducing an initial shape to a target shape , where . We assume that the constructed shapes are equivalent up to translations. In what follows, we restrict attention to and being trees, denoted and , respectively. Throughout, denotes the number of nodes and the number of turning points in . Assuming an arbitrary ordering on the turning points of a tree , let denote the length of segment in . For any pair of geometrically (and, thus, also for topologically) equivalent trees we assume the same ordering; that is, denotes the same segment with lengths and in and , respectively. The input convention assumes that in each segment stores a binary representation of and . We consider the following problem variants. () Single Node Reduction: the system must reduce an initial tree to while avoiding collisions. () Geometrical Reduction: as in (), but now being geometrically equivalent to , with for all segments . () Topological Reduction: as in (), but is additionally topologically equivalent to . () Incompressible Reduction: a restricted case of (), where .
3 Technical Overview
In this section, we present the main results of our work, as shown in Table 1. For single node reduction, we assume common chirality to ensure consistent signal direction across circuits. For incompressible reduction and target tree we additionally assume a unique leader node and a common compass orientation. This allows us to define a direction for each segment (w.l.o.g. and ) and with that an order. All these assumptions can be effectively dropped, as they can be ensured by an additive rounds of preprocessing w.h.p. (see [4]).
Algorithm | Operation | Running Time |
---|---|---|
BFS shrinking | Shrinking | |
Lower bound for | – | |
Incompressible tree (known incompressible nodes) | – | |
Incompressible tree (unknown nodes) | – | |
Optimized BFS shrinking | – | |
Target tree | Shrinking and Growth |
Single Node Reduction.
We present the BFS shrinking algorithm, which reduces an arbitrary tree to a single node. This algorithm consists of three subroutines: () segment detection, () segment coloring and shrinking, and () final segment shrinking.
The segment detection subroutine () allows nodes to detect leaves in their segment by establishing two parallel circuits along each segment . Leaves initiate signals along these circuits, enabling segment nodes to determine the direction toward them. This subroutine ensures common orientation across all segments and completes in rounds. Once segments are detected, the nodes apply the PASC algorithm [9] in the segment coloring and shrinking subroutine () to compute their parity based on their distance from the turning point. Then, nodes alternate colors – blue for even parity and green for odd – after which even-parity nodes absorb adjacent odd-parity nodes, progressively halving each segment’s length (see Figure 1). Subroutine () completes in rounds, where is the length of the segment. The final segment shrinking subroutine () handles the case when is reduced to a single segment. It is not possible to determine an orientation during (), which implies that we cannot decide which endpoint should perform the PASC in subroutine (). So, we perform leader election among the leaves using the parallel circuits from subroutine (), achieving a common orientation in rounds w.h.p.
Theorem 1.
After an -round preprocessing (w.h.p.), the BFS shrinking reduces any tree to a single node in rounds.
A Lower Bound on Geometrical Reduction.
We establish a lower bound on the complexity of reducing geometrically equivalent paths using only shrinking operations. Specifically, we show that some path pairs require rounds, as stated formally below.
Theorem 2.
Let be an algorithm that reduces a path to a geometrically equivalent path . Then there exists an infinite family of pairs of paths of turning points each, for which requires rounds.
Incompressible Reduction.
In the following, we present the incompressible tree algorithm which reduces an initial arbitrary tree to its incompressible form . We assume that each node knows whether it is incompressible and, accordingly, whether it belongs to a compressible column or row. By [1], the incompressible shape is obtained by compressing all compressible columns and rows. To shrink compressible columns and rows, we can apply the segment coloring and shrinking subroutine.
Theorem 3.
Given the incompressible nodes and after an -round preprocessing (w.h.p.), the incompressible tree algorithm reduces to in rounds.
An incompressible tree has at most nodes, as each column and row must contain at least one turning point. Hence, running the incompressible tree algorithm prior to the BFS shrinking algorithm (Theorem 1) yields a runtime of rounds w.h.p.
Remark 4.
If the incompressible nodes are not known in advance, we can compute all incompressible nodes and with that all compressible segments in rounds.
Topological Reduction.
We present the target tree algorithm which reduces an arbitrary tree to another topologically equivalent tree . Let () denote the length of segment in the initial (target) tree. We assume that for each , . Furthermore, we assume that initially, each segment stores .
A challenge in this case is that we cannot simply apply the segment coloring and shrinking subroutine on all segments in parallel. Since doing so does not guarantee that intermediate trees remain topologically equivalent and may lead to collisions. The target tree algorithm consists of three phases: compressible subsegment computation, growth, and shrinking. In the compressible subsegment computation phase, we compute the lengths of all compressible subsegments of each in and and store them in a segment in rounds.
Let and denote the length of the compressible subsegment in the initial and target trees, respectively. In the growth (shrinking) phase, we grow (shrink) all compressible subsegments with (). Observe that it does not matter which nodes exactly perform a growth (shrinking) operation in a segment as long as the number of operations is the same. The idea is therefore to first compute a subsegment for each (the ’s may not be large enough) and then to perform the growth (shrinking) operations of in . Computing the subsegments requires rounds while performing the growth (shrinking) operations requires rounds.
Theorem 5.
After an -round preprocessing (w.h.p.), the target tree algorithm reduces to in rounds.
References
- [1] Nada Almalki, Siddharth Gupta, and Othon Michail. On the exponential growth of geometric shapes. In ALGOWIN, volume 15026 of LNCS, pages 16–30. Springer, 2024. doi:10.1007/978-3-031-74580-5_2.
- [2] Nada Almalki and Othon Michail. On geometric shape construction via growth operations. Theor. Comput. Sci., 984:114324, 2024. doi:10.1016/J.TCS.2023.114324.
- [3] Chen Avin and Stefan Schmid. Toward demand-aware networking: a theory for self-adjusting networks. Comput. Commun. Rev., 48(5):31–40, 2018. doi:10.1145/3310165.3310170.
- [4] Michael Feldmann, Andreas Padalkin, Christian Scheideler, and Shlomi Dolev. Coordinating amoebots via reconfigurable circuits. J. Comput. Biol., 29(4):317–343, 2022. doi:10.1089/CMB.2021.0363.
- [5] Thorsten Götte, Kristian Hinnenthal, Christian Scheideler, and Julian Werthmann. Time-optimal construction of overlay networks. Distributed Comput., 36(3):313–347, 2023. doi:10.1007/S00446-023-00442-4.
- [6] Siddharth Gupta, Marc J. van Kreveld, Othon Michail, and Andreas Padalkin. Collision detection for modular robots - it is easy to cause collisions and hard to avoid them. In ALGOWIN, volume 15026 of LNCS, pages 76–90. Springer, 2024. doi:10.1007/978-3-031-74580-5_6.
- [7] George B. Mertzios, Othon Michail, George Skretas, Paul G. Spirakis, and Michail Theofilatos. The complexity of growing a graph. J. Comput. Syst. Sci., 147:103587, 2025. doi:10.1016/J.JCSS.2024.103587.
- [8] Othon Michail, George Skretas, and Paul G. Spirakis. Distributed computation and reconfiguration in actively dynamic networks. Distributed Comput., 35(2):185–206, 2022. doi:10.1007/S00446-021-00415-5.
- [9] Andreas Padalkin, Christian Scheideler, and Daniel Warner. The structural power of reconfigurable circuits in the amoebot model. Nat. Comput., 23(4):603–625, 2024. doi:10.1007/S11047-024-09981-6.
- [10] Damien Woods, Ho-Lin Chen, Scott Goodfriend, Nadine Dabby, Erik Winfree, and Peng Yin. Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In Innovations in Theoretical Computer Science, ITCS ’13, pages 353–354. ACM, 2013. doi:10.1145/2422436.2422476.