Paper Info
Title
Time optimal asynchronous self-stabilizing spanning tree
Abstract
This paper presents an improved and time-optimal selfstabilizing 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.
Year
DOI
Venue
2007
10.1007/978-3-540-75142-7_10
DISC
Keywords
Field
DocType
realistic model,dynamic network,asynchronous network,previous time-optimal algorithm,time optimal,actual diameter,major task,asynchronous model,network topology,increased asynchrony,time-optimal selfstabilizing algorithm,distributed computing,message passing,spanning tree
Atomicity,Leader election,Asynchronous communication,Distributed minimum spanning tree,Computer science,Real-time computing,Theoretical computer science,Network topology,Spanning tree,Virtual synchrony,Time complexity,Distributed computing
Conference
Volume
ISSN
ISBN
4731
0302-9743
3-540-75141-6
Citations 
PageRank 
References 
23
0.85
24
Authors
2
Name
Order
Citations
PageRank
Janna Burman112313.55
Shay Kutten22118226.75