Please use this identifier to cite or link to this item:
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.
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
Show full item record

Page view(s)

Last Week
Last month
checked on Jun 2, 2023


checked on Jun 2, 2023


Last Week
Last month
checked on Jun 30, 2022

Google ScholarTM


Note about this record

Cite this record


This item is licensed under a Creative Commons License Creative Commons