# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius
Let \(Q\) be the \((d+3)\times(d+3)\) upper left submatrix of \(P\). For \(s=-1,0,1,\ldots,d+1\) denote by \(Q_{s}\) the \((s+2)\times(s+2)\) lower right submatrix of \(Q\), i.e., \(Q=Q_{d+1}\). Denote by \(N_{s}\) the fundamental matrix of \(Q_{s}\) (notation as introduced in Section 5). Let \(1_{s}\) be the column vector of length \((s+2)\) whose entries are all \(1\) and \(\epsilon_{s}=N_{s}1_{s}\). For \(s=0,\ldots,d\), \(\epsilon_{s}\) is the expected number of rounds to reach state \(F\) from state \(C^{d-s}\) and \(\epsilon_{d+1}\) is the expected number of rounds to reach state \(F\) from \(I\), i.e., \(\epsilon_{d+1}=E[A_{d}]\) (Theorem 3.3.5, [12]). Identifying \(P\) with \(C^{d+1}\) we have \(\epsilon_{-1}=1\). **Lemma 15**. : _The expected number \(E[A_{d}]\) of rounds to reach \(F\) from \(I\) is at most \(5\) and the variance is at most \(3.6\)._

Proof. : Note that \(Q_{s}\) and \(N_{s}\) are upper triangle matrices. Let

\[E_{i}-Q_{i}=\left( \begin{array}{cccc}1-a_{1}&-a_{2}&\ldots&-a_{i+2}\\ 0&&\\ \vdots&E_{i-1}-Q_{i-1}\\ 0&&\end{array} \right)\hskip 28.452756 ptN_{i}=\left( \begin{array}{cccc}x_{1}&x_{2}& \ldots&x_{i+2}\\ 0&&\\ \vdots&&N_{i-1}\\ 0&&\end{array} \right)\]

\(E_{i}=(E_{i}-Q_{i})N_{i}\) gives rise to \((i+2)^{2}\) equations. Adding up the \(i+2\) equations for the first row of \(E_{i}\) results in

\[\epsilon_{i}=(1-a_{1})^{-1}\left(1+\sum_{l=2}^{i+2}a_{l}\epsilon_{i+1-l}\right) \tag{1}\]

It is straightforward to verify that \(\epsilon_{-1}=1\) and \(\epsilon_{0}=3\). Hence

\[\epsilon_{i}=(1-a_{1})^{-1}\left(1+\sum_{l=2}^{i}a_{l}\epsilon_{i+1-l}+3a_{i+1} +a_{i+2}\right)\]Next we show by induction on \(i\) that \(\epsilon_{i}\leq 4\) for \(i=-1,0,1,\ldots,d\). So assume that \(\epsilon_{l}\leq 4\) for \(l=-1,0,1,\ldots,i-1\) with \(i<d\). Then

\[\epsilon_{i}\leq(1-a_{1})^{-1}\left(1+4\sum_{l=2}^{i}a_{l}+3a_{i+1}+a_{i+2}\right)\]

since \(a_{i}\geq 0\). Using the fact \(1-a_{1}=\sum_{l=2}^{i+2}a_{l}\) this inequality becomes

\[\epsilon_{i} \leq (1-a_{1})^{-1}(1+4(1-a_{1}-a_{i+1}-a_{i+2})+3a_{i+1}+a_{i+2})=4+ \frac{1-a_{i+1}-3a_{i+2}}{1-a_{1}}\]

Coefficient \(a_{j}\) denotes the transition probability from \(C^{d-i}\) to \(C^{d+j-(i+1)}\) for \(j=1,\ldots,i+1\) and \(a_{i+2}\) that for changing from \(C^{d-i}\) to \(P\). For \(i\leq d\) the following values from Lemma 14 are used:

\[a_{1} = \left(\binom{i}{i+1-l}\left(\frac{1}{2}\right)^{i+1}+\frac{1}{i+1 }\binom{i}{l-1}\left(\frac{1}{4}\right)^{i}(3^{i+1-l}-2^{i+1-l})\right)\] \[a_{i+1} = \left(\frac{1}{2}\right)^{i+1}\text{ and }a_{i+2}=\frac{1}{i+1} \left(\frac{3}{4}\right)^{i}+\frac{i-1}{2(i+1)}.\text{ Thus,}\]

\[3a_{i+2}=\frac{3}{i+1}\left(\frac{3}{4}\right)^{i}+\frac{3(i-1)}{2(i+1)}>1\]

holds for \(i\geq 2\). This yields

\[\frac{1-a_{i+1}-3a_{i+2}}{1-a_{1}}<0\]

and therefore \(\epsilon_{i}\leq 4\). To bound \(\epsilon_{d+1}\) we use Equation 1 with \(i=d+1\). Note that in this case \(a_{1}=0\), since a transition from \(I\) to itself is impossible. Hence

\[E[A_{d}]=\epsilon_{d+1}=1+\sum_{l=2}^{d+3}a_{l}\epsilon_{d+2-l}\leq 1+4\sum_{l=2} ^{d+3}a_{l}=5\]

Thus, \(Var[A_{d}]=((2N_{d+1}-E_{d+1})1_{d+1}-1_{d+1}^{2})[1]=2\sum_{i=1}^{d+3}x_{i} \epsilon_{d+2-i}-\epsilon_{d+1}-\epsilon_{d+1}^{2}\) Figure 6c shows that \(Var[A_{d}]\leq 3.6\). **Lemma 16**. : _The expected containment time after a memory corruption at node \(v\) is at most \(\frac{1}{\ln 2}H_{\delta_{i}(v)}+11/2\) with variance less than 7.5._Proof. : For a set \(X\) of configurations and a single configuration \(c\) denote by \(E(c,X)\) the expected value of the number of transitions from \(x\) to a state in \(X\). Let \(\mathcal{L}\) be the set of legitimate system states.