# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius
Suppose that \(c_{r}=\bot\) and \(v.final=true\) at the round's start. If during the previous round \(v.final\) was set to \(true\) then \(v.c\) can not be \(\bot\) at the start of this round. Hence, at the start of the previous round \(final\) already had value \(true\). But in this case \(v.c\) was not changed in the previous round and thus, \(c_{r}\
eq\bot\), contradiction. Finally assume the last condition. Then \(v\) and \(w\) cannot have changed their value of \(c\) in the previous round, because then \(final=true\) would be impossible at the start of this round. Thus, \(v\) sent \((c_{r},true)\) in the previous round. Hence, if \(w.c=c_{r}\) at that time, \(w\) would have changed \(w.final\) to \(false\), again a contradiction. Lemma 6: _A node setting \(final\) to \(true\) will not change its variables as long as no error occurs._

Proof. : Let \(v\) be a node that executes \(final:=true\). If \(v\) changes the value back to \(false\) in a later round then by Lemma 5 a fault must have occured. Thus in an error-free execution node \(v\) will never change variable \(final\) again. Since a node can only change variable \(c\) if \(final=false\) the proof is complete. Lemma 7: _If at the end of a round during which no error occured each node \(v\) satisfies \(v.final=true\) then the configuration is legitimate and remains legitimate as long as no error occurs._

Proof. : Note that no node changed its color during that round. If at the start of the round \(v.final=true\) was already satisfied then none of \(v\)'s neighbors also having \(final=true\) had the same color as \(v\). Next consider a neighbor \(w\) of \(v\) with \(w.final=false\) at the start of the round. Since \(v\) sent \((v.c,true)\) at the start of this round, node \(w\) would have set \(final\) to \(false\) if it had chosen the same color as \(v\). Contradiction. Finally consider that case that \(v.final=false\) at the start of the round. Since \(v\) changed \(final\) to \(true\), none of its neighbors had chosen the same color as \(v\). Thus, the configuration is legitimate. Obviously, this property can only be changed by a fault. With these lemmas the next theorem is proved along the same lines as Lemma 10.3 in [24]. Theorem 3: _Algorithm \(\mathcal{A}_{col}\) is self-stabilizing and computes a \(\Delta+1\)-coloring within \(O(\log n)\) rounds with high probability (i.e., with probability at least \(1-n^{c}\) for any \(c\geq 1\)). \(\mathcal{A}_{col}\) has contamination radius \(1\)._

Proof. : According to Lemma 7 it suffices to prove that all nodes terminate within \(O(\log n)\) time with high probability. Let \(v\in V\). Lemma 6 implies that the probability that \(v\) terminates in round \(r>1\) is equal to the probability that \(v\) sets \(v.final\) to \(true\) in round \(r-1\). This is the probability that \(v\) selects a color different from \(\bot\) and from the selections of all neighbors that chose a value different from \(\bot\) in round \(r-2\). Suppose that indeed \(v.c\
eq\bot\) at the end of round \(r-2\). Then \(v.c\
ot\in v.tabu\)The probability that a given neighbor \(u\) of \(v\) selects the same color \(u.c=v.c\) in this round is at most \(1/2(\delta(v)+1-|v.tabu|)\). This is because the probability that \(u\) selects a color different from \(\bot\) is \(1/2\), and \(v\) has \(\delta(v)+1-|v.tabu|\) different colors to select from. Since \(r>1\) all nodes in \(v.tabu\) have \(final=true\) and will never change this value. Thus, at most \(\delta(v)-|tabu|\) neighbors select a new color. By the union bound, the probability that \(v\) selects the same color as a neighbor is at most

\[\frac{\delta(v)-|v.tabu|}{2(\delta(v)+1-|v.tabu|)}<\frac{1}{2}.\]

Thus, if \(v\) selects a color \(v.c\
eq\bot\), it is distinct from the colors of its neighbors with probability at least \(1/2\). It holds that \(v.c\
eq\bot\) with probability \(1/2\). Hence, \(v\) terminates with probability at least \(1/4\). The probability that a specific node \(v\) doesn't terminate within \(r\) rounds is at most \((3/4)^{r}\).