Dieses Dokument steht unter einer CreativeCommons Lizenz by/4.0
Verlagslink DOI: doi: 10.3390/a11050058
Titel: Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
Sprache: English
Autor/Autorin: Turau, Volker 
Schlagwörter: distributed algorithms;fault-tolerance;self-stabilization;Markov chain;lumping
Erscheinungsdatum: 3-Mai-2018
Verlag: Multidisciplinary Digital Publishing Institute
Quellenangabe: Algorithms 11 (2018), 5 : 58
Zeitschrift oder Schriftenreihe: Algorithms 
Zusammenfassung (englisch): 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
Sonstige Kennungen: doi: 10.3390/a11050058
Institut: Telematik E-17 
Dokumenttyp: (wissenschaftlicher) Artikel
Sponsor / Fördernde Einrichtung: Deutsche Forschungsgemeinschaft
Projekt: DFG (TU 221/6-2) 
Enthalten in den Sammlungen:Publications (tub.dok)

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat
algorithms-11-00058.pdf947,34 kBAdobe PDFÖffnen/Anzeigen
Zur Langanzeige

Seitenansichten

16
Letzte Woche
0
Letzten Monat
6
checked on 23.03.2019

Download(s)

4
checked on 23.03.2019

Google ScholarTM

Prüfe

Export

Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons