Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.22521 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- The Freeze Tag Problem consists in waking up a swarm of robots starting with one initially awake robot. Whereas there is a wide literature of the centralized setting, where the location of the robots is known in advance, we focus in the distributed version where the location of the robots $¶$ 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 of the whole swarm takes $O(ρ+\ell^2\log( ρ/\ell))$, where $ρ$ stands for the largest distance from the initial robot to any point of $¶$, and the $\ell$ is the connectivity threshold of $¶$. Moreover, the result is complemented by a matching lower bound in both parameters $ρ$ and $\ell$. We also provide other distributed algorithms, complemented with lower bounds, whenever each robot has a bounded amount of energy.