# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius
Therefore, the execution of algorithm \(\mathcal{A}\) can be described by a Markov chain with state set \(\Sigma\) and transition matrix \(P=\left(p_{ij}\right)\), where \(p_{ij}=Prob(\mathcal{A}(c_{i})=c_{j})\) gives the probability to move from configuration \(c_{i}\) to \(c_{j}\in\Sigma\) in one round. This work uses the notation for Markov chains as introduced in [12]. For a self-stabilizing algorithm \(\mathcal{A}\) this Markov chain is denoted by \(\mathcal{C}_{\mathcal{A}}\). In the following we uses the terms configurations of A and states of \(\mathcal{C}_{\mathcal{A}}\) as synonyms. There is a close relation between the absorbing states of \(\mathcal{C}_{\mathcal{A}}\) and the legitimate configurations \(\mathcal{L}\) of \(\mathcal{A}\). The closure property of a self-stabilizing algorithm guarantees that a configuration of \(\mathcal{L}\) is always mapped to a configuration in \(\mathcal{L}\), i.e., \(\mathcal{A}(\mathcal{L})\subseteq\mathcal{L}\). Whereas a state of a markov chain is called absorbing if it is impossible to leave this state. Note that a non-legitimate state of \(\mathcal{A}\) cannot be an absorbing state of \(\mathcal{C}_{\mathcal{A}}\). In silent self-stabilizing algorithms we have \(\mathcal{A}(c)=c\) for all \(c\in\mathcal{L}\). For non-silent algorithms we may without loss of generality also assume that \(\mathcal{A}(c)=c\) for all \(c\in\mathcal{L}\). If this condition is not given we can partition \(\mathcal{L}\) into subsets \(\mathcal{L}_{1},\ldots,\mathcal{L}_{s}\) with \(\mathcal{A}(\mathcal{L}_{i})=\mathcal{L}_{i}\) and identify all configurations in \(\mathcal{L}_{i}\) as corresponding to the same state. For the computation of the stabilization time this does not make a difference. Under this assumption the Markov chain \(\mathcal{C}_{\mathcal{A}}\) is an absorbing Markov chain and the set of absorbing states corresponds to the set of legitimate states of \(\mathcal{A}\). We can state the following easy to prove lemma. **Lemma 3**. : _Let \(c\) be a configuration of \(\mathcal{C}_{\mathcal{A}}\). An absorbing state of \(\mathcal{C}_{\mathcal{A}}\) is reached from \(c\) in expected \(B\) steps if and only if \(\mathcal{A}\) stabilizes in expected \(B\) rounds from \(c\)._

The computation of the expected time to absorption for an absorbing Markov chain using the transition matrix \(P\) is a simple matrix operation [12]. We assume a labeling of the states such that the \(t\) non-absorbing states come before the \(a\) absorbing states. Then \(P\) has the following canonical form

\[P= \begin{pmatrix}Q&R\\ 0&E\end{pmatrix} \]

Here \(E\) is a \(a\times a\) unit matrix and \(Q\) a \(t\times t\) matrix. For an absorbing Markov chain, the matrix \(N=(E-Q)^{-1}\) is called the fundamental matrix for \(P\). Let \(t_{i}\) be the expected number of steps before the chain is absorbed, given that the chain starts in the \(i\)-th state, and let \(t\) be the column vector whose

Figure 2: \(1\)-faulty configurations of \(\mathcal{A}_{1}\) caused by a memory corruption at \(v\). Nodes drawn in bold have state \(IN\). Subgraph \(H\) correspond to \(R_{v}\). In the left graph, if node \(v\) changes to state \(OUT\) then all nodes in \(H\) are enabled, thus the worst case stabilization time is equal to that of subgraph \(H\). In the right graph, if node \(v\) changes to \(IN\), then \(v\) and its two neighboring nodes all change to \(OUT\) resulting in a configuration similar to the previous example. \(i\)-th entry is \(t_{i}\). Then \(t=Nc\), where \(c\) is a column vector all of whose entries are \(1\). The variance of these numbers of steps is given by the entries of \((2N-E)t-t_{sq}\) where \(t_{sq}\) is derived from \(t\) by squaring each entry [12]. Thus, if \(N\) is the fundamental matrix of \(\mathcal{C}_{\mathcal{A}}\) then the expected number of rounds after which algorithm \(\mathcal{A}\) stabilizes is max \(Nc\) provided, the initial configuration is randomly chosen from the non-legitimate configurations. There is still a big obstacles to practically apply this procedure.