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
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;
Conference_Titel :
Reliable Distributed Systems, 2002. Proceedings. 21st IEEE Symposium on
Print_ISBN :
0-7695-1659-9
DOI :
10.1109/RELDIS.2002.1180174
