# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius
Lemma 13: _To find a lower bound for \(E[Z_{d}]\) we may assume that \(w\) can choose a color from \(\{0,1\}\backslash\mathit{tabu}\) with \(\mathit{tabu}=\emptyset\) if \(v.final=false\) and \(\mathit{tabu}=\{v.c\}\) otherwise and \(v\) can choose a color from \(\{0,1,\ldots,d\}\backslash\mathit{tabu}\) with \(\mathit{tabu}\subseteq\{0,1\}\)._

Proof: When a node \(u\in S\) chooses a color with function randomColor the color is randomly selected from \(C_{u}=\{0,1,\ldots,\delta(v)\}\backslash\mathit{tabu}\). Thus, if \(w\) and \(v\) choose colors in the same round, the probability that the chosen colors coincide is \(|C_{w}\cap C_{v}|/|C_{w}||C_{v}|\). This value is maximal if \(|C_{w}\cap C_{v}|\) is maximal and \(|C_{w}||C_{v}|\) is minimal. This is achieved when \(C_{w}\subseteq C_{v}\) and \(C_{v}\) is minimal (independent of the size of \(C_{w}\)) or vice versa. Thus, without loss of generality we can assume that \(C_{w}\subseteq C_{v}\) and both sets are minimal. Thus, for \(w\in N_{\text{conflict}}(v)\) the nodes in \(N(w)\backslash\{v\}\) already use all colors from \(\{0,1,\ldots,\delta(v)\}\) but \(0\) and \(1\) and all nodes in \(N(v)\backslash N_{\text{conflict}}(v)\) already use all colors from \(\{0,1,\ldots,\delta(v)\}\) but \(0,1,\ldots,d\). Hence, a node \(w\in N_{\text{conflict}}(v)\) can choose a color from \(\{0,1\}\backslash\mathit{tabu}\) with \(\mathit{tabu}=\emptyset\) if \(v.final=false\) and \(\mathit{tabu}=\{v.c\}\) otherwise. Furthermore, \(v\) can choose a color from \(\{0,1,\ldots,d\}\backslash\mathit{tabu}\) with \(\mathit{tabu}\subseteq\{0,1\}\). In this case \(\mathit{tabu}=\emptyset\) if \(w.final=false\) for all \(w\in N_{\text{conflict}}(v)\). Thus, in order to bound the expected number of rounds to reach a legitimate state after a memory corruption we can assume that \(G=G_{S}\) and \(u.final=true\) and \(u.c=0\) (i.e., \(c_{f}=0\)) for all \(u\in S\). After one round \(u.final=false\) for all \(u\in S\). To apply Theorem 2.2 the set \(\Sigma\) of all configurations is partitioned into \(d+4\) subsets as follows: \begin{tabular}{l l} \(I\): & Represents the faulty state with \(u.c=0\) and \(u.final=true\) for all \(u\in S\). \\ \(C^{i}\): & Node \(v\) and exactly \(d-i\) non-center nodes will not be in a legitimate state after the following round (\(0\leq i\leq d\)). In particular \(v.final=false\) and \(w.c=v.c\
eq\bot\) or \(v.c=w.c=\bot\) for exactly \(d-i\) non-center nodes \(w\). \\ \(P\): & Node \(v\) has not reached a legitimate state but will do so in the next round. In particular \(v.final=false\) and \(v.c\
eq w.c\) for all non-center nodes \(w\). \\ \(F\): & Node \(v\) is in a legitimate state, i.e., \(v.final=true\) and \(v.c\
eq w.c\) for all non-center nodes \(w\), but \(w.c\) may be equal to \(\bot\). \\ \end{tabular} 

Note that \(I\) is the initial and \(F\) the absorbing state of the lumped Markov chain. Also when the system is in state \(F\), then it is not necessarily in a legitimate state. This state reflects the set of configurations considered in the last section. Lemma 14: _Table 1 describes the transition probabilities of the lumped Markov chain._Proof. : We consider each case separately. The last two cases are trivial. 1. Note that \(u.final=true\) and \(u.c=0\) for all \(u\in S\). Case 0: \(v.c=\bot\). Impossible. Case 1: \(v.c=0\). Impossible, since non-center nodes have \(c=0\) and \(final=true\). Case 2: \(v.c=1\). This happens with probability \(1/2d\). All non-center nodes \(w\) choose \(w.c=\bot\), this happens with probability \(1/2^{d}\). Case 3: \(v.c>1\). This happens with probability \((d-1)/(2d)\). Non-center nodes can make any choice. This gives the total probability for this transition as \((d-1)/(2d)+1/(d2^{d+1})\). 2. Note that \(u.final=true\) and \(u.c=0\) for all \(u\in S\). Case 0: \(v.c=\bot\). Non-center nodes choose \(c=\bot\). The case has probability \(1/2^{d+1}\) Case 1: \(v.c=0\). Impossible (see transition \(I\longrightarrow P\)). Case 2: \(v.c=1\).