# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius
: \[p(\Sigma_{i},\Sigma_{j})=\sum_{c\in\Sigma_{j}}p(c_{i},c).\]2 \[p(\Sigma_{i},\Sigma_{j})=\sum_{c\in\Sigma_{j}}p(c_{i},c).\]3 \[p(\Sigma_{i},\Sigma_{j})=\sum_{c\in\Sigma_{j}}p(c_{i},c).\]4 \[p(\Sigma_{i},\Sigma_{j})=\sum_{c\in\Sigma_{j}}p(c_{i},c).\]5 \[p(\Sigma_{i},\Sigma_{j})=\sum_{c\in\Sigma_{j}}p(c_{i},c).\]6 \[p(\Sigma_{i},\Sigma_{j})=\sum_{c\in\Sigma_{j}}p(c_{i},c).\]7

For the first equation we refer to the proof of Theorem 4. The second equality makes use of

\[p(\Sigma_{i},\Sigma_{j})=\sum_{c\in\Sigma_{j}}p(c_{i},c).\]8

and the fourth equality uses the following two identities

\[p(\Sigma_{i},\Sigma_{j})=\sum_{c\in\Sigma_{j}}p(c_{i},c).\]9

**Lemma 12**. : _Let \(d>0\) and \(q\in(0,1)\) then_

Figure 3:0

Proof. : We approximate \(\sum\
olimits_{l=1}^{\infty}{l(1-(1-q^{l})^{d})}\) with \(\int_{0}^{\infty}{x(1-(1-q^{x})^{d})}{lx}\). Note that \(x(1-(1-q^{x})^{d})\) has a single local maximum in the interval \([0,\infty)\). If the local maximum is within the interval \([y,y+1]\) with \(y\in\mathbb{N}\) then the error is

Figure 3:1This leads to a small overestimation of the sum as Figure 6b shows. Figure 3:2 Figure 3:3 Figure 3:4 Figure 3:5

The first equation uses the substitution \(u=1-q^{x}\). The final result is based on the following identity

Figure 3:6

Theorem 4 gives an upper bound for the containment time and its variance of algorithm \(\mathcal{A}_{col}\). To evaluate the quality of these upper bounds we modeled the behavior of this fault situation as a Markov chain and computed \(E[X_{d}]\) and \(Var[X_{d}]\) using a software package based on symbolic mathematics. Using Theorem 3.3.5 from [12] these computations showed that \(\frac{1}{\ln 2}H_{d}+1/2\) matches very well with \(E[X_{d}]\) and that \(E[X_{d}]\approx 2\log d\) (see Figure 6a). Furthermore, the gap between \(Var[X_{d}]\) and the bound given in Theorem 4 is less than 0.2 (see Figure 6b). ### Memory Corruption

This section demonstrates the use of Markov chains and the application of Theorem 2. We consider the case that the memory of a single node \(v\) is hit by a fault. The analysis breaks down the stabilizing executions into several states and then computes the expected time for each of these phases. First we look at the case that the fault causes variable \(v.final\) to change to \(false\). If \(v.c\) does not change, then a legitimate configuration is reached after one round. So assume \(v.c\) also changes. Then the fault will not affect other nodes. This is because no \(w\in N(v)\) will change its value of \(w.c\) since \(w.final=true\) and \(v.final=false\). Thus, with probability at least 1/2 node \(v\) will choose in the next round a color different from the colors of all neighbors and terminate one round later. Similar to \(X_{d}\) let random

Figure 3:7 Comparisons of computed with approximated values from Theorems 4 and 15. **(a)** Comparison of computed value of \(E[X_{d}]\) with \(\log d\) (Theorem 4); **(b)** Comparison of computed value of \(Var[X_{d}]\) with approximation (Theorem 4); **(c)**\(E[A_{d}]\) and \(Var[A_{d}]\) from Lemma 15.

variable \(Z_{d}\) denote the number of rounds until a legal coloring is reached (\(d=|N_{\text{conflict}}(v)|\)). It is easy to verify that \(E[Z_{d}]=3\) in this case. The last case is that only variable \(v.c\) is affected (i.e., \(v.final\) remains \(true\)). The main difference to the case of a corrupted message is that this fault persists until \(v.c\) has again a legitimate value. Let \(c_{f}\) be the corrupted value of \(v.c\) and suppose that \(N_{\text{conflict}}(v)=\{w\in N(v)\mid w.c=c_{f}\}\
eq\emptyset\). A node outside \(S=N_{\text{conflict}}(v)\cup\{v\}\) will not change its state (cf. Lemma 8). Thus, the contamination radius is \(1\) and at most \(\delta_{i}(v)+1\) nodes change state. Let \(d=|N_{\text{conflict}}(v)|\). The subgraph \(G_{S}\) induced by \(S\) is a star graph with \(d+1\) nodes and center \(v\).