Deterministic Self-Stabilizing BFS Construction in Constant Space
Lélia Blin, Franck Petit, Sébastien Tixeuil · 2025
Read Deterministic Self-Stabilizing BFS Construction in Constant Space by Lélia Blin, Franck Petit, Sébastien Tixeuil (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-06596.txt.
Description
Blin, Petit, and Tixeuil settle a long-standing question in distributed computing in a 2025 paper. Self-stabilizing algorithms recover from any starting mess on their own. Building a breadth-first spanning tree with only constant memory per node seemed impossible.
Their synchronous algorithm does exactly that, with just a constant number of memory bits per node. It needs no knowledge of network size, diameter, or degree. Convergence time scales with the root's eccentricity in an exponential bound they state. A constant-space token scheme wipes out cycles and fixes structural errors. Older methods leaned on neighbor pointers or distance counters that break the memory cap. The authors say memory-starved systems are the real target. The result reopens protocol design under tight limits.
Catalog record
| CREATOR | Lélia Blin, Franck Petit, Sébastien Tixeuil |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-06596