DocumentCode
3065662
Title
An exercise in proving self-stabilization through Lyapunov functions
Author
Theel, Oliver
Author_Institution
Dept. of Comput. Sci., Darmstadt Univ. of Technol., Germany
fYear
2001
fDate
36982
Firstpage
727
Lastpage
730
Abstract
Self-stabilizing distributed algorithms exhibit interesting analogies with the stabilizing feedback systems that are used in various engineering domains. In this paper, we show, with E.W. Dijkstra´s (1974) token-ring algorithm for mutual exclusion serving as an example, that methodologies from control theory, e.g. Lyapunov´s “second method”, can be used to more easily and systematically prove the self-stabilization property of distributed algorithms
Keywords
Lyapunov methods; control theory; distributed algorithms; feedback; functions; stability; token networks; Lyapunov functions; Lyapunov´s 2nd method; control theory; engineering domains; mutual exclusion; self-stabilizing distributed algorithms; stabilizing feedback systems; token-ring algorithm; Algorithm design and analysis; Computer science; Control systems; Control theory; Distributed algorithms; Feedback; Mechanical engineering; Mechanical factors; Reactive power; Token networks;
fLanguage
English
Publisher
ieee
Conference_Titel
Distributed Computing Systems, 2001. 21st International Conference on.
Conference_Location
Mesa, AZ
Print_ISBN
0-7695-1077-9
Type
conf
DOI
10.1109/ICDSC.2001.919010
Filename
919010
Link To Document