DocumentCode
390024
Title
Fault-local stabilization : the shortest path tree
Author
Beauquier, J. ; Hèrault, T.
Author_Institution
Lab. de Recherche en Informatique, Univ. Paris XI, Orsay, France
fYear
2002
fDate
2002
Firstpage
62
Lastpage
69
Abstract
We present a fault-local solution to the shortest path tree problem in a rooted network. We consider the case where a transient fault corrupts f nodes (f is unknown, but inferior to half the size of the network) after the tree has been constructed. Our solution allows to recover in less than O (f) time units. If an upper bound k on the number of corrupted nodes is known, the memory space needed depends only on k.
Keywords
computer networks; fault tolerant computing; fault-local error handling; fault-local solution; rooted network; shortest path tree; stabilization; transient fault; voting based protocol; Algorithm design and analysis; Communication channels; Costs; Design methodology; Protocols; Tree graphs; Upper bound; Voting;
fLanguage
English
Publisher
ieee
Conference_Titel
Reliable Distributed Systems, 2002. Proceedings. 21st IEEE Symposium on
ISSN
1060-9857
Print_ISBN
0-7695-1659-9
Type
conf
DOI
10.1109/RELDIS.2002.1180174
Filename
1180174
Link To Document