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

CREATORLélia Blin, Franck Petit, Sébastien Tixeuil
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE78 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-06596

Browse the full library · About the Tower of Babel