Please use this identifier to cite or link to this item:
https://doi.org/10.15480/882.1925
Publisher DOI: | 10.3390/a11050058 | Title: | Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains | Language: | English | Authors: | Turau, Volker | Keywords: | distributed algorithms; fault-tolerance; self-stabilization; Markov chain; lumping | Issue Date: | 3-May-2018 | Publisher: | Multidisciplinary Digital Publishing Institute | Source: | Algorithms 11 (2018), 5 : 58 | Abstract (english): | 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. |
URI: | http://tubdok.tub.tuhh.de/handle/11420/1928 | DOI: | 10.15480/882.1925 | ISSN: | 1999-4893 | Journal: | Algorithms | Other Identifiers: | doi: 10.3390/a11050058 | Institute: | Telematik E-17 | Document Type: | Article | Project: | Tolerance-Zone - Fehlertolerante Middleware-Idiome basierend auf selbststabilisierenden Techniken Fehlertolerante verteilte Algorithmen |
More Funding information: | Deutsche Forschungsgemeinschaft | License: | ![]() |
Appears in Collections: | Publications with fulltext |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
algorithms-11-00058.pdf | 947,34 kB | Adobe PDF | View/Open![]() |
Page view(s)
306
Last Week
2
2
Last month
4
4
checked on Jun 2, 2023
Download(s)
264
checked on Jun 2, 2023
SCOPUSTM
Citations
2
Last Week
0
0
Last month
0
0
checked on Jun 30, 2022
Google ScholarTM
Check
Note about this record
Cite this record
Export
This item is licensed under a Creative Commons License