# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius
The following theorem gives a bound for the expected value of the containment time including its variance. Since the variance of a random variable is the expected value of the squared deviation from the mean, this theorem shows that the containment time does not deviate much from its expected value. A concrete bound can be obtained from this result using Chebyshev's inequality. Theorem 3.4: _The expected containment time of algorithm \(\mathcal{A}_{col}\) after a corruption of a message broadcast by node \(v\) is at most \(\frac{1}{\text{m}2}H_{\delta_{i}(v)}+1/2\) rounds (\(H_{i}\) is the \(i^{\text{th}}\) harmonic number) with a variance of at most_

\[\frac{1}{\text{m}^{2}}2\sum_{i=1}^{\delta(v)}\frac{1}{i^{2}}+\frac{1}{4}\leq \frac{\pi^{2}}{6\ln^{2}2}+\frac{1}{4}\approx 3.6737.\]

Proof. : After receiving message \((c_{f},true)\) all nodes \(w\in N_{\text{conflict}}(v)\) set \(w.final\) to \(false\) and with equal probability \(w.c\) to \(\bot\) or to a random color \(c_{w}\in\{0,1,\dots,\delta(w)\}\backslash w.tabu\). Note that \(|w.tabu|\leq\delta(w)\) because \(w.tabu=\{u.c\mid u\in N(w)\backslash v\}\cup\{c_{f}\}\). At the end of the round during which the corrupted message was received, node \(w\) can choose \(v\)'s current color, because it may not be contained in the set \(tabu\). This can not happen in the following rounds. Thus, if \(w\) chooses a color different from \(\bot\) in the following rounds then this color is different from the colors of all of \(w\)'s neighbors. Also in this case \(w\) will terminate after the following round because then it will set \(final\) to \(true\). Thus, after one round \(w\) has chosen a color that is different from the colors of all neighbors with probability at least \(1/2\). Furthermore, this color will not change again. After one additional round \(w\) reaches a legitimate state. Let the random variable \(X_{d}\) with \(d=|N_{\text{conflict}}(v)|\) denote the number of rounds until the system has reached a legal coloring. For \(w\in N_{\text{conflict}}(v)\) let \(Y_{w}\) be the random variable denoting the number of rounds until \(w\) has a legal coloring. By Lemma 8\(X_{d}=\max\{Y_{w}\mid w\in N_{\text{conflict}}(v)\}\). For \(i\geq 1\) let \(G(i)=Prob(X_{d}\leq i)=Prob(\max\{Y_{w}\mid w\in N_{\text{conflict}}(v)\}\leq i)\). Since the random variables \(Y_{w}\)'s are independent \(G(i)=Prob(X\leq i)^{|N_{\text{conflict}}(v)|}\) where \(X\) is a geometric random variable with \(p=0.5\). Thus \(G(0)=0\) and

\[G(i)=\left(\sum_{j=1}^{i}p(1-p)^{j-1}\right)^{d}.\]



**Lemma 9**. : _For fixed \(0<q<1\) and fixed \(d\geq 1\)_

\[\sum_{c\in\Sigma_{j}}p(c_{1},c)=\sum_{c\in\Sigma_{j}}p(c_{2},c).\]0

Proof. : The function \(f(x)=1-(1-q^{x})^{d}\) is for fixed values of \(d\) decreasing for \(x\geq 0\). Furthermore, \(f(0)=1.\) Hence,

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

Using the substitution \(u=1-q^{x}\) the integral becomes

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

Approximating \(\int_{i}^{i+1}f(x)dx\) with \((f(i)+f(i+1))/2\) yields

\[\sum_{c\in\Sigma_{j}}p(c_{1},c)=\sum_{c\in\Sigma_{j}}p(c_{2},c).\]3

**Lemma 10**. : _For \(d>0\) the variance of the containment time is at most_

\[\sum_{c\in\Sigma_{j}}p(c_{1},c)=\sum_{c\in\Sigma_{j}}p(c_{2},c).\]4

Proof. : \[\sum_{c\in\Sigma_{j}}p(c_{1},c)=\sum_{c\in\Sigma_{j}}p(c_{2},c).\]5

By Lemma 11

\[\sum_{c\in\Sigma_{j}}p(c_{1},c)=\sum_{c\in\Sigma_{j}}p(c_{2},c).\]6

Now Lemma 12 and Lemma 4 yield

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

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

**Lemma 11**. : _Let \(d>0\), \(q\in(0,1)\) and \(Prob(X=i)=\sum\limits_{j=1}^{d}{d\choose j}\frac{(-1)^{j+1}(1-q^{j})}{q^{j}}(q^{j })^{i}\). Then_

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

Proof.