Options
Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
Citation Link: https://doi.org/10.15480/882.1925
Publikationstyp
Journal Article
Date Issued
2018-05-03
Sprache
English
Author(s)
Institut
TORE-DOI
Journal
Volume
11.2018, 5
Start Page
Artikelnummer: 58
Citation
Algorithms 11 (2018), 5 : 58
Publisher DOI
Scopus ID
Publisher
Multidisciplinary Digital Publishing Institute
The analysis of self-stabilizing algorithms is often limited to the worst case stabilization time starting from an arbitrary state, i.e., a state resulting from a sequence of faults. Considering the fact that these algorithms are intended to provide fault tolerance in the long run, this is not the most relevant metric. A common situation is that a running system is an a legitimate state when hit by a single fault. This event has a much higher probability than multiple concurrent faults. Therefore, the worst case time to recover from a single fault is more relevant than the recovery time from a large number of faults. This paper presents techniques to derive upper bounds for the mean time to recover from a single fault for self-stabilizing algorithms based on Markov chains in combination with lumping. To illustrate the applicability of the techniques they are applied to a new self-stabilizing coloring algorithm.
Subjects
distributed algorithms
fault-tolerance
self-stabilization
Markov chain
lumping
DDC Class
510: Mathematik
More Funding Information
Deutsche Forschungsgemeinschaft
Loading...
Name
algorithms-11-00058.pdf
Size
947.34 KB
Format
Adobe PDF