Distributed Freeze Tag: a sustainable solution to discover and wake-up a robot swarm

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.