# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 1 Introduction  
Fault tolerance aims at making distributed systems more reliable by enabling them to continue the provision of services in the presence of faults. The strongest form is _masking fault tolerance_, where a system continues to operate after faults without any observable impairment of functionality, i.e., safety is always guaranteed. In contrast _non-masking fault tolerance_ does not ensure safety at all times. Users may experience incorrect system behavior, but eventually the system will fully recover. The potential of this concept lies in the fact that it can be used in cases where masking fault tolerance is too costly or even impossible to implement [1]. _Self-stabilizing algorithms_ belong to the category of distributed algorithms that provide non-masking fault tolerance. They guarantee that systems eventually recover from transient faults of any scale such as perturbations of the state in memory or communication message corruption [2]. A critical issue is the length of the time span until full recovery. Examples are known where a memory corruption at a single process caused a vast disruption in large parts of the system and triggered a cascade of corrections to reestablish safety. Thus, an important issue for non-masking fault tolerance is the containment of the effect of faults. A _fault-containing_ system has the ability to contain the effects of transient faults in space and time. The goal is to keep the extent of disruption during recovery proportional to the extent of the faults. An extreme case of fault-containment with respect to space is given when the effect of faults is bounded to the set of faulty nodes. [PERSON] et al. call this _error confinement_[3]. More relaxed forms of fault-containment are known as time-adaptive self-stabilization [4], scalable self-stabilization [5], strong stabilization [6], and 1-adaptive self-stabilization [7]. A configuration is called _\(k\)-faulty_, if in a legitimate configuration exactly _\(k\)_ processes are hit by a fault (a configuration is called _legitimate_ if it conforms with the specification). A large body ofresearch focuses on fault-containment for 1-faulty configurations. Two metrics have been introduced to quantify the containment behavior in the 1-faulty case: _contamination radius_ and _containment time_[8; 9]. A distributed algorithm \(\mathcal{A}\) has contamination radius \(r\) if only nodes within the \(r\)-hop neighborhood of the faulty node change their state during recovery from a 1-faulty configuration. The containment time of \(\mathcal{A}\) denotes the worst-case number of rounds any execution of \(\mathcal{A}\) starting at a 1-faulty configuration needs to reach a legitimate configuration. In technical terms this corresponds to the _worst case time to recover_ in case of a single fault. For randomized algorithms the expected number of rounds to reach a legitimate configuration corresponds to the _mean time to recover_ (MTTR). Over the last two decades a large number of self-stabilizing algorithms have been published. Surprisingly the analysis of the vast majority of these algorithms is confined to the worst case stabilization time starting from an arbitrary configuration. Considering the fact that these algorithms are intended to provide fault tolerance in the long run this is not the most relevant metric at all. From a practical point of view the recovery time from a 1-faulty configuration is more interesting. This statement is justified considering the fact that the probability for a 1-faulty configuration is much higher than that for a \(k\)-faulty configuration with a large value of \(k\). The reason is that a distributed system consists of independently operating computers where transient faults such as memory faults in different computers are independent events. Considering this fact it comes as a surprise that most papers consider only arbitrary initial states (i.e., \(k\)-faulty configuration for any \(k\)) instead of focusing on 1-faulty configuration.