# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius
By the union bound, the probability that there exists a vertex \(v\in V\) that does not terminate within \(r\) rounds is at most \(n(3/4)^{r}\). Hence, \(\mathcal{A}_{col}\) terminates after \(r=(c+1)4\log n\) rounds, with probability at least \(1-n(3/4)^{r}\geq 1-1/n^{c}\) (note that \(\log 4/3>1/4\)). ### Fault Containment Time of Algorithm \(\mathcal{A}_{col}\)

There is a significant difference between the shared memory and the message passing model when analyzing the containment time. Firstly, a 1-faulty configuration also arises when a single message sent by a node \(v\) is corrupted. Secondly, this may cause \(v\)'s neighbors to send messages they would not send in a legitimate configuration. Even though the states of nodes outside \(G_{v}^{r}\) do not change, these nodes may be forced to send messages. Thus, in general the analysis of the containment time cannot be performed by considering \(G_{v}^{r}\) only. This is only possible in cases when a fault at \(v\) does not force nodes at distance \(r+1\) to send messages they would not send had the fault not occurred. In the following the fault containment behavior of \(\mathcal{A}_{col}\) for 1-faulty configurations is analyzed. Two types of transient errors are considered:

1. A single broadcast message sent by \(v\) is corrupted. Note that the alternative of using \(\delta(v)\) unicast messages instead a single broadcast has very good fault containment behavior but is slower due to the handling of acknowledgements. 2. Memory corruption at node \(v\), i.e., the value of at least one of the two variables of \(v\) is corrupted. The first case is analyzed analytically whereas for the second case Markov chains and lumping. (Theorem 2) are used. The _independent degree_\(\delta_{i}(v)\) of a node \(v\) is the size of a maximum independent set of \(N(v)\). Let \(\Delta_{i}(G)=\max\{\delta_{i}(v)\mid v\in V\}\). ### Message Corruption

If a message broadcast by \(v\) contains a color \(c_{f}\) different from \(v.c\) or the value \(false\) for variable \(final\) then the message \((c_{f},false)\) has no effect on any \(w\in N(v)\) regardless of the value of \(c_{f}\), since \(w.final=true\) for all \(w\in N(v)\). Thus, this corrupted message has no effect at all. In order to compute the containment time for \(\mathcal{A}_{col}\) we first compute the contamination radius. Lemma 8: _The contamination radius of algorithm \(\mathcal{A}_{col}\) after a single corruption of a broadcast message sent by node \(v\) is \(1\). At most \(\delta_{i}(v)\) nodes change their state during recovery._

Proof: It suffices to consider the case that \(v\) broadcasts message \((c_{f},true)\) with \(c_{f}\
eq v.c\). Let \(N_{\text{conflict}}(v)=\{w\in N(v)\mid w.c=c_{f}\}\). The nodes in \(N_{\text{conflict}}(v)\) form an independent set, because they all have the same color. Thus \(|N_{\text{conflict}}(v)|\leq\delta_{i}(v)\). Let \(u\in V\backslash N[v]\). This node continues to send \((u.c,true)\) after the fault. Thus, a neighbor of \(u\) that changes its color will not change its color to \(u.c\). This yields that no neighbor of \(u\) will ever send a message with \(u.c\) as the first parameter. This is also true in case \(u\in N(v)\backslash N_{\text{conflict}}(v)\). Hence, no node outside \(N_{\text{conflict}}(v)\cup\{v\}\) will change its state, i.e., the contamination radius is \(1\). Let \(w\in N_{\text{conflict}}(v)\). When \(w\) receives the faulty message it sets \(w.final\) to false. Before the faulty message was sent no neighbor of \(v\) had the same color as \(v\). Thus, in the worst case a node \(w\in N_{\text{conflict}}(v)\) will choose \(v.c\) as its new color and send \((v.c,false)\) to all neighbors. Since \(v.final=true\), this will not force state to change at \(v\). Thus, \(v\) keeps broadcasting \((v.c,true)\) and no neighbor \(w\) of \(v\) will ever reach the state \(w.c=v.c\) and \(w.final=true\). Hence, \(v\) will never change its state. With this result Theorem 3 implies that the containment time of this fault is \(O(\log\delta_{i}(v))\) on expectation.