Turau, VolkerVolkerTurau2018-12-132018-12-132018-05-03Algorithms 11 (2018), 5 : 58http://tubdok.tub.tuhh.de/handle/11420/1928The 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.en1999-48932018Artikelnummer: 58Multidisciplinary Digital Publishing Institutehttps://creativecommons.org/licenses/by/4.0/distributed algorithmsfault-toleranceself-stabilizationMarkov chainlumpingMathematikJournal Article2018-11-22urn:nbn:de:gbv:830-882.02385410.15480/882.192511420/192810.3390/a1105005810.15480/882.1925Journal Article