DocumentCode :
3259694
Title :
An automatic approach to self-stabilization
Author :
Hamid, Brahim ; Mosbah, Mohamed
Author_Institution :
ENSEIRB, Bordeaux Univ., Talence, France
fYear :
2005
fDate :
23-25 May 2005
Firstpage :
123
Lastpage :
128
Abstract :
We present a formal method to design self-stabilizing algorithms by using graph rewriting systems (GRS). This method is based on two phases. The first phase consists of defining the set of illegitimate configurations (GRSIC). The second phase allows to construct some local correction rules to eliminate the illegitimate configurations. Then the graph relabeling system composed of the initial graph rewriting system improved with the addition of the correction rules is a self-stabilizing system (LSGRS). We obtain a general approach to deal with fault-tolerance in distributed computing. We illustrate our approach by various self-stabilizing algorithms for computing distributed spanning trees and SSP´s algorithm.
Keywords :
distributed processing; fault tolerant computing; formal specification; graph grammars; rewriting systems; correction rule construction; distributed computing; fault-tolerance; formal method; graph relabeling system; graph rewriting systems; illegitimate configurations; self-stabilization; Algorithm design and analysis; Design methodology; Distributed computing; Fault tolerance; Tree graphs;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, 2005 and First ACIS International Workshop on Self-Assembling Wireless Networks. SNPD/SAWN 2005. Sixth International Conference on
Print_ISBN :
0-7695-2294-7
Type :
conf
DOI :
10.1109/SNPD-SAWN.2005.14
Filename :
1434877
Link To Document :
بازگشت