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: CC BY 4.0 (Attribution) CC BY 4.0 (Attribution)
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
algorithms-11-00058.pdf947,34 kBAdobe PDFView/Open
Thumbnail
Show full item record

Page view(s)

306
Last Week
2
Last month
4
checked on Jun 2, 2023

Download(s)

264
checked on Jun 2, 2023

SCOPUSTM   
Citations

2
Last Week
0
Last month
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 Creative Commons