# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius
At least one non-center nodes \(w\) choose \(w.c=1\), all others choose \(w.c=\bot\). This case has probability \(\frac{1}{2d}\sum_{l=1}^{d}\binom{d}{l}\left(\frac{1}{2}\right)^{d}=\frac{1}{2 d}\left(\frac{1}{2}\right)^{d}(2^{d}-1)\). Case 3: \(v.c>1\). This case is impossible. 3. Note that \(u.final=true\) for all \(u\in S\). Case 1: \(v.c=0\). This happens with probability \(1/2(d-i+1)\). None of the \(d-i\) non-center nodes \(w\) sets \(w.c=0\), this has probability \(\left(\frac{3}{4}\right)^{d-i}\). Case 2: \(v.c=1\). Similar to case 1. Case 3: \(v.c>1\). (requires \(d-i>1\)). This happens with probability \(\frac{d-i-1}{2(d-i+1)}\). Non-center nodes can make any choice. 4. Note that \(u.final=false\) for all \(u\in S\). Case 1: \(v.c=\bot\). This happens with probability \(\frac{1}{2}\). \(d-j\) non-center nodes choose \(c=\bot\) (with probability \(1/2^{d-j}\)), the other \(j-i\) non-center nodes choose \(c\
eq\bot\) (with probability \(1/2^{j-i}\)). The total probability for this case is \(\binom{d-i}{d-j}\left(\frac{1}{2}\right)^{d-i+1}\). Case 2: \(v.c=0\). This happens with probability \(1/(2(d-i+1))\). Exactly \(j-i\) non-center nodes choose \(c=1\) (with probability \(1/4^{j-i}\)), \(1\leq l\leq d-j\) non-center nodes choose \(c=0\) \begin{table}
\begin{tabular}{c c c} \hline \hline
**Number** & **Transition** & **Probability** \\ \hline
1 & \(I\longrightarrow P\) & \(\frac{d-1}{2d}+\frac{1}{d}\left(\frac{1}{2}\right)^{d+1}\) \\
2 & \(I\longrightarrow C^{0}\) & \(\frac{d-1}{d}\left(\frac{1}{2}\right)^{d+1}+\frac{1}{2d}\) \\
3 & \(I\longrightarrow C^{j}\) & \(\binom{d}{d-j}\left(\frac{1}{2}\right)^{d+1}(0<j\leq d)\) \\
4 & \(C^{i}\longrightarrow C^{j}\) & \(\binom{d-i}{d-j}\left(\frac{1}{2}\right)^{d-i+1}+\frac{1}{d-i+1}(\binom{d-i}{ j-i}\left(\frac{1}{4}\right)^{d-i}(3^{d-j}-2^{d-j})\) (\(0\leq i\leq j\leq d\)) \\
5 & \(C^{i}\longrightarrow P\) & \(\frac{1}{d-i+1}\left(\frac{3}{4}\right)^{d-i}+\frac{d-i-1}{2(d-i+1)}\) (\(0\leq i<d\)) \\
6 & \(C^{d}\longrightarrow P\) & \(1/2\) \\
7 & \(P\longrightarrow F\) & \(1\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: This table summarizes the probabilities for all transitions. (with probability \(1/4^{l}\)) and all other non-center nodes choose \(c=\bot\) (with probability \(1/2^{d-j-l}\)). The total probability for this case is \[ \begin{array}{ll}&\frac{1}{2(d-i+1)}(\sfrac{d-i}{j-i})\left(\frac{1}{4} \right)^{j-i}\sum_{l=1}^{d-j}\sfrac{d-i}{l}\left(\frac{1}{4}\right)^{l}\left( \frac{1}{2}\right)^{d-j-l}\\ =&\frac{1}{2(d-i+1)}(\sfrac{d-i}{j-i})\left(\frac{1}{4}\right)^{j-i}\sum_{l=1} ^{d-j}\sfrac{d-j}{l}\left(\frac{1}{2}\right)^{d-j+l}\\ =&\frac{1}{2(d-i+1)}(\sfrac{d-i}{j-i})\left(\frac{1}{4}\right)^{j-i}\left( \frac{1}{2}\right)^{d-j}\sum_{l=1}^{d-j}\sfrac{d-j}{l}\left(\frac{d-j}{l} \right)\left(\frac{1}{2}\right)^{l}\\ =&\frac{1}{2(d-i+1)}(\sfrac{d-i}{j-i})\left(\frac{1}{2}\right)^{d+j-2i}\sum_{ l=1}^{d-j}\sfrac{d-j}{l}\left(\frac{d-j}{l}\right)\left(\frac{1}{2}\right)^{l}\\ =&\frac{1}{2(d-i+1)}(\sfrac{d-i}{j-i})\left(\frac{1}{2}\right)^{d+j-2i}\left( \left(\frac{3}{2}\right)^{d-j}-1\right)\\ =&\frac{1}{2(d-i+1)}(\sfrac{d-i}{j-i})\left(\frac{1}{4}\right)^{d-i}\left(3^{ d-j}-2^{d-j}\right)\end{array} \] Case 2: \(v.c=1\). Similar to Case 1. Case 3: \(v.c>0\). This does not lead to \(C^{l}\) but to \(P\). 5. Note that \(u.final=false\) for all \(u\in S\). Case 1: \(v.c=0\). This happens with probability \(1/2(d-i+1)\). None of the \(d-i\) non-center nodes \(w\) sets \(w.c=0\), this has probability \(\left(3/4\right)^{d-i}\). Case 2: \(v.c=1\). Similar to case 1. Case 3: \(v.c>1\). This happens with probability \(\frac{d-i-1}{2(d-i+1)}\). Note \(d>i\). Non-center nodes can make any choice. We first calculate the expected number \(E[A_{d}]\) of rounds to reach the absorbing state \(F\). With Theorem 4 this will enable us to compute the expected number \(E[Z_{d}]\) of rounds required to reach a legitimate system state. To build the transition matrix of the lumped Markov chain the \(d+4\) states are ordered as \(I,C^{0},C^{1},\ldots,C^{d},P,F\).