# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius
The presented techniques can also be applied to other randomized coloring algorithms such as [17; 20; 21]. The main difference is that \(\mathcal{A}_{col}\) assumes the synchronous \(\mathcal{CONGEST}\) message passing model. Algorithm \(\mathcal{A}_{col}\) stabilizes after \(O(\log n)\) rounds with high probability whereas the above cited self-stabilizing algorithms all require a linear number of rounds. Since synchronous local algorithms can be converted to asynchronous self-stabilizing algorithms [25], there are self-stabilizing \(\Delta+1\)-coloring algorithms faster than \(\mathcal{A}_{col}\). However, they entail a burden on memory resources and cause high traffic costs. At the start of each round each node broadcasts its current color to its neighbors. Based on the information received from its neighbors a node decides either to keep its color (final choice), to choose a new color or no color (value \(\bot\)). In particular, with equal probability a node \(v\) draws uniformly at random a color from the set \(\{0,1,\ldots,\delta(v)\}\backslash\mathit{tabu}\) or indicates that it made no choice (see function randomColor). Here, \(\mathit{tabu}\) is the set of colors of neighbors of \(v\) that already made their final choice. ```
Set<Color> tabu := \(\emptyset\), occupied := \(\emptyset\);  broadcast(c, final) to all neighbors w \(\in\) N(v); for all neighbors w \(\in\) N(v)do  receive(c\({}_{w}\), final\({}_{w}\)) from node \(w\); if\(c_{w}\
eq\bot\)then  occupied := occupied \(\cup\)\(\{c_{w}\}\); if\(\mathit{final}_{w}\)then\(\mathrm{tabu}:=\mathrm{tabu}\cup\{c_{w}\}\) ; if\(\mathit{c}=\bot\lor c>\delta(v)\)then  final := false; else if\(\mathit{final}\)then if\(\mathit{c}\in\mathit{tabu}\)then\(\mathrm{final}\) := false ; else if\(\mathit{c}\
ot\in\mathit{occupied}\)then\(\mathrm{final}\) := true ; if\(\mathit{final}\) = false then\(\mathrm{c}:=\mathrm{randomColor}(\mathit{v},\mathit{tabu})\) ; functionColorrandomColor(Node \(v\), Set<Color> tabu) ifrandom bit from 0,1 = 1 thenreturn\(\bot\) ; return random color from \(\{0,1,\ldots,\delta(v)\}\backslash\mathrm{tabu}\);
```

**Algorithm 4**Algorithm \(\mathcal{A}_{col}\) as executed by a node \(v\) in each round. In the original algorithm a node maintains a list with the colors of those neighbors that made their final choice. A fault changing this list is difficult to contain. Furthermore, in order to notice a memory corruption at a neighbor, each node must continuously send its state to all its neighbors and cannot stop to do so. This is the price of self-stabilization and well known [2]. These considerations lead to the design of Algorithm \(\mathcal{A}_{col}\). Each node only maintains the chosen color and whether its choice is final (variables c and final). In every round a node sends the values of c and final to all neighbors. \(\mathcal{A}_{col}\) uses two additional variables tabu and occupied. They are reset at the beginning of every round. To improve fault containment a node's final choice of a color is only withdrawn if it coincides with the final choice of a neighbor. To achieve a \(\Delta+1\)-coloring a node makes a new choice if its color is larger than its degree. This situation can only originate from a fault. First we prove correctness and analyze the stabilization time of \(\mathcal{A}_{col}\). A configuration is called a _legal coloring_ if the values of variable \(c\) form a \(\Delta+1\)-coloring. It is called _legitimate_ if it is a legal coloring and \(v.final=true\) for each node \(v\). Lemma 5: _A node \(v\) can change the value of variable \(final\) from \(true\) to \(false\) only in the first round or when a fault occured just before the start of this round._

Proof. : Let \(v.c=c_{r}\) at the beginning of the round. In order for \(v\) to set \(v.final\) to \(false\) one of the following conditions must be met at the start of the round: \(c_{r}>\delta(v)\), \(c_{r}=\bot\), or \(v\) has a neighbor \(w\) with \(w.final=true\) and \(w.c=c_{r}\). The lemma is obviously true in the first case.