We consider geometric collision-detection problems for modular reconfigurable robots. Assuming the nodes (modules) are connected squares on a grid, we investigate the complexity of deciding whether collisions may occur, or can be avoided, if a set of expansion and contraction operations is executed. We study both discrete- and continuous-time models, and allow operations to be coupled into a single parallel group. Our algorithms to decide if a collision may occur run in O ( n 2 log 2 n ) time, O ( n 2 ) time, or O ( n log 2 n ) time, depending on the presence and type of coupled operations, in a continuous-time model for a modular robot with n nodes. To decide if collisions can be avoided, we show that a very restricted version is already NP-complete in the discrete-time model, while the same problem is polynomial in the continuous-time model. A less restricted version is NP-hard in the continuous-time model.

A temporal graph 𝒢 = (G,λ) can be represented by an underlying graph G = (V,E) together with a function λ that assigns to each edge e ∈ E the set of time steps during which e is present. The reachability graph of 𝒢 is the directed graph D = (V,A) with (u,v) ∈ A if and only if there is a temporal path from u to v. We study the Reachability Graph Realizability (RGR) problem that asks whether a given directed graph D = (V,A) is the reachability graph of some temporal graph. The question can be asked for undirected or directed temporal graphs, for reachability defined via strict or non-strict temporal paths, and with or without restrictions on λ (simple, proper, or both). Answering an open question posed by Casteigts et al. (TCS 2024), we show that all variants of the problem are NP-complete, except for two variants that become trivial in the directed case. For undirected temporal graphs, we consider the complexity of the problem with respect to the solid graph, that is, the graph containing all edges that could potentially receive a label in any realization. We show that the RGR problem is fixed-parameter tractable for the feedback edge set number of the solid graph. As we show, the latter parameter can presumably not be replaced by smaller parameters like feedback vertex set number or treedepth, since the problem is W[2]-hard for them.

Balancing resource efficiency and fairness is critical in networked systems that support modern learning applications. We introduce the _Fair Minimum Labeling_ (FML) problem: the task of designing a minimum-cost temporal edge activation plan that ensures each group of nodes in a network has sufficient access to a designated target set, according to specified coverage requirements. FML captures key trade-offs in systems where edge activations incur resource costs and equitable access is essential, such as distributed data collection, update dissemination in edge-cloud systems, and fair service restoration in critical infrastructure. We show that FML is NP-hard and $\Omega(\log |V|)$-hard to approximate, where $V$ is the set of nodes, and we present probabilistic approximation algorithms that match this bound, achieving the best possible guarantee for the activation cost. We demonstrate the practical utility of FML in a fair multi-source data aggregation task for training a shared model. Empirical results show that FML enforces group-level fairness with substantially lower activation cost than baseline heuristics, underscoring its potential for building resource-efficient, equitable temporal reachability in learning-integrated networks.

We study a new algorithmic process of graph growth which starts from a single initial vertex and operates in discrete time-steps, called slots . In every slot, the graph grows via two operations (i) vertex generation and (ii) edge activation. The process completes at the last slot where a (possibly empty) subset of the edges of the graph are removed. Removed edges are called excess edges . The main problem investigated in this paper is: Given a target graph G , design an algorithm that outputs a process that grows G , called a growth schedule . Additionally, we aim to minimize the total number of slots k and of excess edges ℓ used by the process. We provide both positive and negative results, with our main focus being either schedules with sub-linear number of slots or with no excess edges.

In this paper, we explore the exponential growth of geometric structures starting from a single node, focusing on centralized growth operations. We identify a parameter k , representing the number of turning points within specific parts of a shape. We prove that, if edges can only be formed between a newly generated node and the node that created it and cannot be deleted, trees having at most k turning points on every root-to-leaf path can be grown in O ( k log ⁡ k + log ⁡ n ) time steps and spirals with O ( log ⁡ n ) turning points can be grown in O ( log ⁡ n ) time steps, n being the size of the final shape. For this model, we also show that the maximum number of turning points in a root-to-leaf path of a tree is a lower bound on the number of time steps to grow the tree and that there exists a class of paths such that any path in the class with k turning points requires Ω ( k log ⁡ k ) time steps to be grown. If nodes can additionally be connected as soon as they become adjacent, we prove that if a shape S has a spanning tree with at most k turning points on every root-to-leaf path, then the adjacency closure of S can be grown in O ( k log ⁡ k + log ⁡ n ) time steps. In the strongest version of the model, where, additionally, edges can be deleted and neighbors handed over to new nodes, we present a universal algorithm for growing any shape S exponentially fast.

In this paper, we study the main open question of [Michail, Skretas, Spirakis, ICALP'17], asking what are the families of two-dimensional geometric shapes, drawn on a square grid, that can be transformed into each other by a sequence of rotation operations, none of which disconnects the shape. The model represents programmable matter systems consisting of interconnected robotic modules that perform the minimal mechanical operation of 90° rotations around each other. The goal is to transform an initial connected shape of modules A into a target connected shape B . Under the necessary assumption that the two shapes have identical colour cardinalities on a checkered colouring of the grid, and using at most a constant number of auxiliary modules to trigger the transformation, we prove that almost any pair of such shapes can be transformed into each other within an optimal O ( n 2 ) rotation operations none of which disconnects the shape.

We study algorithmic growth processes under a geometric setting. Each process begins with an initial shape of nodes SI=S0 and, in every time step t≥1, by applying (in parallel) one or more growth operations of a specific type to the current shape, St−1, generates the next, St, always satisfying |St|>|St−1|. We define three types of growth operations and explore the algorithmic and structural properties of their resulting processes. Our goal is to characterize the classes of shapes that can be constructed in O(log⁡n) or polylog n time steps, n being the size of the final shape SF. Moreover, we want to determine whether a given shape SF can be constructed from a given initial shape SI using a finite sequence of growth operations of a given type, called a constructor of SF. We give exact and partial characterizations of classes of shapes that can be constructed in polylog n time steps, polynomial-time centralized algorithms for deciding reachability between pairs of input shapes (SI,SF) and for generating constructors when SF can be constructed from SI, as well as some negative results.

We consider a discrete system of n simple indistinguishable devices, called agents, forming a connected shape SI on a two-dimensional square grid. Agents are equipped with a linear-strength mechanism, called a line move, by which an agent can push a whole line of consecutive agents in one of the four cardinal directions in a single time-step. We study the problem of transforming an initial shape SI into a given target shape SF via a finite sequence of line moves in a distributed model, where each agent can observe the states of nearby agents in a Moore neighbourhood. We develop the first distributed connectivity-preserving transformation that exploits line moves. The transformation solves the line formation problem. That is, starting from any shape SI whose associated graph contains a Hamiltonian path known to them, the agents can form a final straight line SL. The complexity of the transformation is O(nlog2⁡n) moves, which is asymptotically equivalent to that of the best-known centralised transformations.

Abstract We study here systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration to carry out a given task. Also, the distributed task itself may now require a global reconfiguration from a given initial network $$G_s$$ G s to a target network $$G_f$$ G f from a desirable family of networks. To formally capture costs associated with creating and maintaining connections, we define three edge-complexity measures: the total edge activations , the maximum activated edges per round , and the maximum activated degree of a node . We give (poly)log( n ) time algorithms for the task of transforming any $$G_s$$ G s into a $$G_f$$ G f of diameter (poly)log( n ), while minimizing the edge-complexity. Our main lower bound shows that $$\varOmega (n)$$ Ω ( n ) total edge activations and $$\varOmega (n/\log n)$$ Ω ( n / log n ) activations per round must be paid by any algorithm (even centralized) that achieves an optimum of $$\varTheta (\log n)$$ Θ ( log n ) rounds. We give three distributed algorithms for our general task. The first runs in $$O(\log n)$$ O ( log n ) time, with at most 2 n active edges per round, a total of $$O(n\log n)$$ O ( n log n ) edge activations, a maximum degree $$n-1$$ n - 1 , and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations. It gives a target network of diameter $$O(\log n)$$ O ( log n ) and uses O ( n ) active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog( n ) then we can achieve $$o(\log ^2 n)$$ o ( log 2 n ) running time. </

We study a model of programmable matter systems consisting of n devices lying on a 2-dimensional square grid which are able to perform the minimal mechanical operation of rotating around each other. The goal is to transform an initial shape A into a target shape B. We investigate the class of shapes which can be constructed in such a scenario under the additional constraint of maintaining global connectivity at all times. We focus on the scenario of transforming nice shapes, a class of shapes consisting of a central line L where for all nodes u in S either u∈L or u is connected to L by a line of nodes perpendicular to L. We prove that by introducing a minimal 3-node seed it is possible for the canonical shape of a line of n nodes to be transformed into a nice shape of n−1 nodes. We use this to show that a 4-node seed enables the transformation of nice shapes of size n into any other nice shape of size n in O(n2) time. We leave as an open problem the expansion of the class of shapes which can be constructed using such a seed to include those derived from nice shapes.

In this paper, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration in order to carry out a given task. At the same time, the distributed task itself may now require a global reconfiguration from a given initial network Gs to a target network Gf from a family of networks having some good properties, like small diameter.

In this work we consider temporal networks, i.e. networks defined by a labeling $$\lambda $$ assigning to each edge of an underlying graphG a set of discrete time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on path problems of temporal networks. In particular, we consider time-respecting paths, i.e. paths whose edges are assigned by $$\lambda $$ a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a natural analogue of Menger’s theorem holding for arbitrary temporal networks. Finally, we propose two cost minimization parameters for temporal network design. One is the temporality of G, in which the goal is to minimize the maximum number of labels of an edge, and the other is the temporal cost of G, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some connectivity constraint. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.

We study population protocols: networks of anonymous agents whose pairwise interactions are chosen uniformly at random. The size counting problem is that of calculating the exact number n of agents in the population, assuming no leader (each agent starts in the same state). We give the first protocol that solves this problem in sublinear time. The protocol converges in O(log n log log n) time and uses O(n^60) states (O(1) + 60 log n bits of memory per agent) with probability 1-O((log log n)/n). The time to converge is also O(log n log log n) in expectation. Crucially, unlike most published protocols with omega(1) states, our protocol is uniform: it uses the same transition algorithm for any population size, so does not need an estimate of the population size to be embedded into the algorithm.

In this work, we consider a solution of automata (or nodes ) that move passively in a well-mixed solution without being capable of controlling their movement. Nodes can cooperate by interacting in pairs and every such interaction may result in an update of their local states. Additionally, the nodes may also choose to connect to each other in order to start forming some required structure. Such nodes can be thought of as small programmable pieces of matter , like tiny nanorobots or programmable molecules. The model that we introduce here is a more applied version of network constructors, imposing physical (or geometric ) constraints on the connections that the nodes are allowed to form. Each node can connect to other nodes only via a very limited number of local ports . Connections are always made at unit distance and are perpendicular to connections of neighboring ports , which makes the model capable of forming 2D or 3D shapes . We provide direct constructors for some basic shape construction problems, like spanning line , spanning square , and self-replication . We then develop new techniques for determining the computational and constructive capabilities of our model. One of the main novelties of our approach is that of exploiting the assumptions that the system is well-mixed and has a unique leader, in order to give terminating protocols that are correct with high probability . This allows us to develop terminating subroutines that can be sequentially composed to form larger modular protocols . One of our main results is a terminating protocol counting the size n of the system with high probability. We then use this protocol as a subroutine in order to develop our universal constructors , establishing that it is possible for the nodes to become self-organized with high probability into arbitrarily complex shapes while still detecting termination of the construction .

In this work, we study the following basic question: “How much parallelism does a distributed task permit?” Our definition of parallelism (or symmetry) here is not in terms of speed, but in terms of identical roles that processes have at the same time in the execution. For example, we may ask: “Can a given task be solved by a protocol that always has at least two processes in the same role at the same time?” (i.e., by a protocol that never elects a unique leader). We choose to initiate this study in population protocols, a very simple model that not only allows for a straightforward definition of what a role is, but also encloses the challenge of isolating the properties that are due to the protocol from those that are due to the adversary scheduler, who controls the interactions between the processes. In particular, we define the role of a process at a given time to be equivalent to the state of the process at that time. Moreover, we isolate the symmetry that is due to the protocol (inherent symmetry) by focusing on those schedules that maximize symmetry for that protocol and observing how much symmetry breaking the protocol is forced to achieve in order to solve the problem. To allow for such symmetry maximizing schedules we consider parallel schedulers that in every step may select a whole collection of pairs of nodes (up to a perfect matching) to interact and not just a single pair. Based on these definitions of symmetric computation, we (i) give a partial characterization of the set of predicates on input assignments that can be stably computed with maximum symmetry, i.e., $$\Theta (N_{min})$$ , where $$N_{min}$$ is the minimum multiplicity of a state in the initial configuration, and (ii) we turn our attention to the remaining predicates (that have some essentially different properties) and prove a strong impossibility result for the parity predicate: the inherent symmetry of any protocol that stably computes it is upper bounded by a constant that depends on the size of the protocol. The latter immediately generalizes to a subset of the predicates that are not closed under doubling.

In this work, we study theoretical models of programmable matter systems. The systems under consideration consist of spherical modules, kept together by magnetic forces and able to perform two minimal mechanical operations (or movements): rotate around a neighbor and slide over a line. In terms of modeling, there are n nodes arranged in a 2-dimensional grid and forming some initial shape. The goal is for the initial shape A to transform to some target shape B by a sequence of movements. Most of the paper focuses on transformability questions, meaning whether it is in principle feasible to transform a given shape to another. We first consider the case in which only rotation is available to the nodes. Our main result is that deciding whether two given shapes A and B can be transformed to each other is in P. We then insist on rotation only and impose the restriction that the nodes must maintain global connectivity throughout the transformation. We prove that the corresponding transformability question is in PSPACE and study the problem of determining the minimum seeds that can make feasible otherwise infeasible transformations. Next we allow both rotations and slidings and prove universality: any two connected shapes A,B of the same number of nodes, can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is Theta(n^2). We improve this to O(n) parallel time, by a pipelining strategy, and prove optimality of both by matching lower bounds. We next turn our attention to distributed transformations. The nodes are now distributed processes able to perform communicate-compute-move rounds. We provide distributed algorithms for a general type of transformation.

In this work, we consider a solution of automata similar to Population Protocols and Network Constructors. The automata, also called nodes, move passively in a well-mixed solution and can cooperate by interacting in pairs. During every such interaction, the nodes, apart from updating their states, may also choose to connect to each other in order to start forming some required structure. The model introduced here is a more applied version of Network Constructors, imposing geometrical constraints on the permissible connections. Each node can connect to other nodes only via a very limited number of local ports, which implies that at any given time it has only a bounded number of neighbors. Connections are always made at unit distance and are perpendicular to connections of neighboring ports. Though this variation can no longer form abstract networks, it is still capable of forming very practical 2D or 3D shapes. We develop new techniques for determining the computational and constructive capabilities of our model. One of the main novelties, concerns our attempt to overcome the inherent inability of such systems to terminate. In particular, exploiting the assumptions that the system is well-mixed and has a unique leader, we give terminating protocols that are correct with high probability (w.h.p.). This allows us to develop terminating subroutines that can be sequentially composed to form larger modular protocols. One of our main results is a terminating protocol counting the size n of the system w.h.p.. We then use this protocol as a subroutine in order to develop our universal constructors, establishing that it is possible for the nodes to self-organize w.h.p. into arbitrarily complex shapes and additionally always terminate.

In this work, we study protocols so that populations of distributed processes can construct networks. In order to highlight the basic principles of distributed network construction we keep the model minimal in all respects. In particular, we assume finite-state processes that all begin from the same initial state and all execute the same protocol. Moreover, we assume pairwise interactions between the processes that are scheduled by a fair adversary. In order to allow processes to construct networks, we let them activate and deactivate their pairwise connections. When two processes interact, the protocol takes as input the states of the processes and the state of their connection and updates all of them. Initially all connections are inactive and the goal is for the processes, after interacting and activating/deactivating connections for a while, to end up with a desired stable network. We give protocols (optimal in some cases) and lower bounds for several basic network construction problems such as spanning line, spanning ring, spanning star, and regular network. The expected time to convergence of our protocols is analyzed under a uniform random scheduler. Finally, we prove several universality results by presenting generic protocols that are capable of simulating a Turing Machine (TM) and exploiting it in order to construct a large class of networks. We additionally show how to partition the population into k supernodes, each being a line of log k nodes, for the largest such $k$. This amount of local memory is sufficient for the supernodes to obtain unique names and exploit their names and their memory to realize nontrivial constructions.

We propose a new theoretical model for passively mobile wireless sensor networks, called P M , standing for passively mobile machines . The main modification w.r.t. the population protocol model (Angluin et al., 2006) [30] is that agents now, instead of being automata, are Turing Machines. We provide general definitions for unbounded memories, but we are mainly interested in computations upper-bounded by plausible space limitations. However, we prove that our results hold for more general cases. We focus on complete interaction graphs and define the complexity classes PMSPACE ( f ( n ) ) parametrically, consisting of all predicates that are stably computable by some PM protocol that uses O ( f ( n ) ) memory in each agent. We provide a protocol that generates unique identifiers from scratch only by using O ( log n ) memory, and use it to provide an exact characterization of the classes PMSPACE ( f ( n ) ) when f ( n ) = Ω ( log n ) : they are precisely the classes of all symmetric predicates in NSPACE ( n f ( n ) ) . As a consequence, we obtain a space hierarchy of the PM model when the memory bounds are Ω ( log n ) . We next explore the computability of the PM model when the protocols use o ( log log n ) space per machine and prove that SEM = PMSPACE ( f ( n ) ) when f ( n ) = o ( log log n ) , where SEM denotes the class of the semilinear predicates. Finally, we establish that the minimal space requirement for the computation of non-semilinear predicates is O ( log log n ) .