Computing fault-containment times of self-stabilizing algorithms using lumped Markov chains (Q2283837): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.3390/a11050058 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2801164407 / rank | |||
Normal rank |
Revision as of 03:25, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computing fault-containment times of self-stabilizing algorithms using lumped Markov chains |
scientific article |
Statements
Computing fault-containment times of self-stabilizing algorithms using lumped Markov chains (English)
0 references
13 January 2020
0 references
Summary: 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.
0 references
distributed algorithms
0 references
fault-tolerance
0 references
self-stabilization
0 references
Markov chain
0 references
lumping
0 references