Title :
Analyzing self-stabilization with finite-state machine model
Author :
Hsu, Su-Chu ; Huang, Shing-Tsaan
Author_Institution :
Inst. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
Abstract :
An approach to analyzing self-stabilization based on the finite-state machine model is presented. A finite-state machine is used to model the behavior of each node in a distributed system. when the self-stabilizing algorithms are applied. The approach is useful for analyzing the correctness of self-stabilizing algorithms and their time complexity. A self-stabilizing algorithm for finding maximal matching is used as an example to show how the finite-state machine model is applied. A simpler proof for the correctness and an upper bound of the time complexity tighter than the one proved by a variant function are attained
Keywords :
computational complexity; fault tolerant computing; finite state machines; distributed system; finite-state machine model; maximal matching; self-stabilisation; time complexity; variant function; Algorithm design and analysis; Computer science; Contracts; Councils; Distributed algorithms; Fault detection; Fault tolerant systems; Protocols; Tree data structures; Upper bound;
Conference_Titel :
Distributed Computing Systems, 1992., Proceedings of the 12th International Conference on
Conference_Location :
Yokohama
Print_ISBN :
0-8186-2865-0
DOI :
10.1109/ICDCS.1992.235106
