# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius
In order to compute the matrix \(N\) the probabilities \(p_{i,j}\) need to be known explicitly. Without knowing the graph explicitly it is impossible to compute the probabilities \(p_{i,j}=Prob(\mathcal{A}(c_{i})=c_{j})\) for all pairs of states \(c_{i},c_{j}\). This is only possible for small graphs or when the graph has a symmetric structure, e.g., a ring. The fundamental matrix contains a lot of information which is not needed for the computation of the stabilization time. Therefore, a coarser analysis of the Markov chain would be sufficient. A common approach is to partition \(\Sigma\) into subsets \(\Sigma_{0},\ldots,\Sigma_{l}\) and consider these as the states of a new Markov chain (see Figure 3). The challenge is to define the transition probabilities of the new chain in a way that allows to transfer properties of this new chain to the original one. A partition \(P=\{\Sigma_{0},\ldots,\Sigma_{l}\}\) of \(\Sigma\) is called _lumpable_ if the subsets \(\Sigma_{i}\) have the property that for each pair \(i,j\) the probability of a state \(c\in\Sigma_{i}\) to be transformed in one step into a state of \(\Sigma_{j}\) is independent of the choice of \(c\in\Sigma_{i}\) (Definition 6.3.1 [12]). This probability is then interpreted as the transition probability from \(\Sigma_{i}\) to \(\Sigma_{j}\). More formally, a Markov chain is _lumpable_ with respect to partition \(P=\{\Sigma_{0},\ldots,\Sigma_{l}\}\) of \(\Sigma\) if for any \(\Sigma_{i},\Sigma_{j}\in P\) and any \(c_{1},c_{2}\in\Sigma_{i}\)

\[\sum_{c\in\Sigma_{j}}p(c_{1},c)=\sum_{c\in\Sigma_{j}}p(c_{2},c).\]

A lumpable Markov \(\mathcal{C}\) chain defines a new Markov chain \(\mathcal{C}^{P}\) with state set \(P\) and transition probabilities

\[p(\Sigma_{i},\Sigma_{j})=\sum_{c\in\Sigma_{j}}p(c_{i},c).\]

The following result proved in [12], p. 128. **Lemma 4**. : _Let \(c\in\Sigma_{i}\) be a state of a lumpable Markov chain \(\mathcal{C}\). Then the expected time to reach from \(c\) an absorbing state of \(\mathcal{C}\) is equal to the expected time to reach from \(\Sigma_{i}\) an absorbing state of \(\mathcal{C}^{P}\)._

The last two lemmas prove the following theorem. **Theorem 1**. : _Let \(\mathcal{A}\) be a self-stabilizing algorithm with \(\Sigma\) the set of configurations. Let \(P=\{\Sigma_{0},\ldots,\Sigma_{l}\}\) be a partition of \(\Sigma\) with \(\Sigma_{0}=\mathcal{L}\) such that \(\mathcal{C}_{\mathcal{A}}\) is lumpable with respect to \(P\). For any \(i\) an absorbing state of \(\mathcal{C}_{\mathcal{A}}^{P}\) is reached from \(\Sigma_{i}\) in expected \(B\) steps if and only if \(\mathcal{A}\) stabilizes in expected \(B\) rounds starting in any \(c\in\Sigma_{i}\)._

Figure 3: Reducing the number of states of a Markov chain. Unfortunately it is rather difficult to make use of Theorem 1 under general conditions. This situations changes when the theorem is used to compute the containment time of a self-stabilizing algorithm \(\mathcal{A}\). Remember that the containment time of \(\mathcal{A}\) denotes the worst-case number of rounds any execution of \(\mathcal{A}\) starting in a 1-faulty configuration needs to reach a legitimate configuration. Thus, the containment time of \(\mathcal{A}\) is \(ST_{\mathcal{A}}(R_{\triangledown})\), where \(v\) is the faulty node. There are two aspects that ease the application of Theorem 1: Either \(R_{\triangledown}\) has a symmetric structure or \(R_{\triangledown}\) is small. To illustrate this approach we consider again algorithm \(\mathcal{A}_{3}\). Let \(v\) be a node that changes in a legitimate state its color to \(c_{f}\) due to a memory fault (see Figure 4). Let \(c_{0}\) be the new configuration. This causes a conflict with those neighbors of \(v\) that had chosen \(c_{f}\) as their color. After the fault only nodes contained in \(R_{\triangledown}\) (a star graph) change their state (see Figure 4 right). Once a neighbor has chosen a color different from \(c_{f}\) then it becomes passive (at least until the next transient fault).