Options
Computing the fault-containment time of self-stabilizing algorithms using Markov chains and lumping
Publikationstyp
Conference Paper
Date Issued
2017-10-07
Sprache
English
Author(s)
Institut
TORE-URI
First published in
Number in series
10616 LNCS
Start Page
62
End Page
77
Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (10616 LNCS): 62-77 (2017)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Springer
The analysis of self-stabilizing algorithms is in the vast majority of all cases limited to the worst case stabilization time starting from an arbitrary configuration. Considering the fact that these algorithms are intended to provide fault tolerance in the long run this is not the most relevant metric. From a practical point of view the worst case time to recover in case of a single fault is much more crucial. This paper presents techniques to derive upper bounds for the mean time to recover from a single fault for self-stabilizing algorithms Markov chains in combination with lumping. To illustrate the applicability of the techniques they are applied to a self-stabilizing coloring algorithm.
DDC Class
004: Informatik
380: Handel, Kommunikation, Verkehr
More Funding Information
Funded by Deutsche Forschungsgemeinschaft DFG (TU 221/6-1).