Time Optimal Asynchronous Self-stabilizing Spanning Tree 92-107, 2007
Burman, Janna Kutten, Shay
Abstract:
This paper presents an improved and time-optimal self-stabilizing algorithm for a major task in distributed computing- a rooted
spanning tree construction. Our solution is decentralized (“truly distributed”), uses a bounded memory and is not based on the
assumption that either n (the number of nodes), or diam (the actual diameter of the network), or an existence of cycles in the
network are known. The algorithm assumes asynchronous
and reliable FIFO message passing and unique identifiers, and works in dynamic networks and for any network topology.
One of the previous time-optimal algorithms for this task was designed for a model with coarse-grained atomic operations and
can be shown not to work properly for the totally asynchronous model (with just “read” or “receive” atomicity, and “write”
or “send” atomicity). We revised the algorithm and proved it for a more realistic model of totally asynchronous networks.
The state in the presented algorithm does not stabilize until long after the required output does. For such an algorithm,
an increased asynchrony poses much increased hardness in the proof.