In the standard Freeze-Tag Problem (FTP), an initially awake robot (the source) is in charge of waking up a swarm of sleeping robots by moving towards them, given that all the awake robots can participate in the awakening process. The goal is to minimize the makespan to wake up all robots assuming they move at unit speed. In this paper we introduce the Freeze-Tag-with-Return Problem (FTRP) variant, where the robots must eventually return to their initial positions. In the Euclidean plane with n sleeping robots lying on the unit disk centered at the initial position of the source, we show a non-trivial relationship between FTP and FTRP by proving that the difference between the optimal makespan of both problems never exceeds 1.959, and is at least 1.732 in the worst-case. We also present several upper and lower bounds on the optimal makespan. In particular, we show that if the sleeping robots are in convex positions, then the optimal makespan is at most 2 + 2√2, which is achieved by some instances. From an algorithmic point-of-view, we present single-exponential algorithms for general distance functions. In metric spaces, these algorithms are asymptotically optimal under the ETH, which we show via an NP-hardness reduction on unweighted graphs.

The Freeze-Tag Problem consists in waking up a swarm of robots starting with one initially awake robot. While there exists a wide literature on the centralized setting, where the locations of the robots are known in advance, we focus on the distributed version where the locations of the robots, P, are unknown, and where awake robots only detect other robots up to distance 1. Assuming that moving at distance δ takes a time δ, we show that waking up the whole swarm takes O(ρ + ℓ2 log(ρ/ℓ)), where ρ is the largest distance from the initial robot to any point of P, and ℓ is the connectivity threshold of P. Moreover, the result is complemented by a matching lower bound. We also provide other distributed algorithms, complemented with lower bounds, whenever each robot has a bounded amount of energy.

We address the problem of Termination Detection (TD) in asynchronous networks. It is known that TD cannot be achieved in the context of self-stabilization, except in the specific case where the TD algorithm is snap-stabilizing, i.e., it always behaves according to its specification regardless of the initial configuration. In this paper, we propose a generic, deterministic, snap-stabilizing, silent algorithm that detects whether an observed terminating silent self-stabilizing algorithm, A, has converged to a configuration that satisfies an intended predicate. Our algorithm assumes that nodes know (an upper bound on) the network diameter D. However, it requires no underlying structure, nor specific topology (arbitrary network), and works in anonymous networks, i.e., our algorithm uses no kind of assumption allowing distinguishing one or more nodes. Furthermore, it works under the weakest scheduling assumptions a.k.a, the unfair daemon. Built over any asynchronous self-stabilizing underlying unison U, our solution adds only O(log D) bits per node. Since there exists no unison algorithm with better space complexity, the extra space of our solution is negligible w.r.t. the space complexity of the underlying unison algorithm. Our algorithm provides a positive answer in O(max (k, k’, D)) time units, where k and k’ are the stabilization time complexities of A and U, respectively.

Algorithms for mutual exclusion aim to isolate potentially concurrent accesses to the same shared resources. Motivated by distributed computing research on programmable matter and population protocols where interactions among entities are often assumed to be isolated, Daymude, Richa, and Scheideler (SAND`22) introduced a variant of the local mutual exclusion problem that applies to arbitrary dynamic networks: each node, on issuing a lock request, must acquire exclusive locks on itself and all its persistent neighbors, i.e., the neighbors that remain connected to it over the duration of the lock request. Assuming adversarial edge dynamics, semi-synchronous or asynchronous concurrency, and anonymous nodes communicating via message passing, their randomized algorithm achieves mutual exclusion (non-intersecting lock sets) and lockout freedom (eventual success with probability 1). However, they did not analyze their algorithm’s runtime. In this paper, we prove that any node will successfully lock itself and its persistent neighbors within 𝒪(nΔ³) open rounds of its lock request in expectation, where n is the number of nodes in the dynamic network, Δ is the maximum degree of the dynamic network, rounds are normalized to the execution time of the "slowest" node, and "closed" rounds when some persistent neighbors are already locked by another node are ignored (i.e., only "open" rounds are considered).

In the context of self-stabilization, a silent algorithm guarantees that the communication registers (a.k.a register) of every node do not change once the algorithm has stabilized. At the end of the 90’s, Dolev et al. [Acta Inf. '99] showed that, for finding the centers of a graph, for electing a leader, or for constructing a spanning tree, every silent deterministic algorithm must use a memory of Omega(log n) bits per register in n-node networks. Similarly, Korman et al. [Dist. Comp. '07] proved, using the notion of proof-labeling-scheme, that, for constructing a minimum-weight spanning tree (MST), every silent algorithm must use a memory of Omega(log^2n) bits per register. It follows that requiring the algorithm to be silent has a cost in terms of memory space, while, in the context of self-stabilization, where every node constantly checks the states of its neighbors, the silence property can be of limited practical interest. In fact, it is known that relaxing this requirement results in algorithms with smaller space-complexity. In this paper, we are aiming at measuring how much gain in terms of memory can be expected by using arbitrary deterministic self-stabilizing algorithms, not necessarily silent. To our knowledge, the only known lower bound on the memory requirement for deterministic general algorithms, also established at the end of the 90’s, is due to Beauquier et al. [PODC '99] who proved that registers of constant size are not sufficient for leader election algorithms. We improve this result by establishing the lower bound Omega(log log n) bits per register for deterministic self-stabilizing algorithms solving (Delta+1)-coloring, leader election or constructing a spanning tree in networks of maximum degree Delta.