# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius  
Consider an algorithm in the shared memory model with contamination radius \(r\). A single fault will not spread beyond the \(r\)-hop neighborhood of the faulty node \(v\). In this case \(R_{v}\subseteq G_{v}^{r}\); \(G_{v}^{r}\) is the subgraph induced by nodes \(w\) with \(dist(v,w)\leq r\). As an example consider the well known self-stabilizing algorithm \(\mathcal{A}_{1}\) to compute a maximal independent set (see Algorithm 1). It uses a single variable \(state\). A configuration is legitimate if nodes with \(state=IN\) form a maximal independent set. ```
if\(state=IN\land\exists w\in N(v)\)s.t. \(w.state=IN\)then\(\quad



Due to its choice of a new color from the palette algorithm \(\mathcal{A}_{2}\) has contamination radius at least \(\Delta(G)\) (see Figure 1). A minor modification of algorithm \(\mathcal{A}_{2}\) dramatically changes matters. Algorithm \(\mathcal{A}_{3}\) (see Algorithm 3) has contamination radius 1 (see Lemma 2). Note that neighbors of \(v\) that change their color during recovery form an independent set. ```
if\(\exists w\in N(v)\) s.t. \(c=w.c\)then ifrandom bit from 0,1 = 1 then \(c:=\) choose \(\{0,\ldots,\Delta\}\backslash\{w.c\mid w\in N(v)\}\)
```
**Algorithm 3**Self-stabilizing \(\Delta+1\)-coloring algorithm \(\mathcal{A}_{3}\). **Lemma 2**. : _Algorithm \(\mathcal{A}_{3}\) has contamination radius one._

Proof. : Consider a \(1\)-faulty configuration where node \(v\) is hit by a memory corruption changing its color to a color \(c\) already chosen by at least one neighbor of \(v\). Let \(N_{\text{conflict}}=\{w\in N(v)\mid w.c=c\}\). In the next round the nodes in \(N_{\text{conflict}}\cup\{v\}\) will get a chance to choose a new color. The choices will only lead to conflicts between \(v\) and other nodes in \(N_{\text{conflict}}\). Thus, the fault will not spread beyond the set \(N_{\text{conflict}}\). With a positive probability the set \(N_{\text{conflict}}\) will contain fewer nodes in each round. ### Containment Time

As the contamination radius the containment time strongly depends on the concrete structure of \(G\). This can be illustrated with algorithm \(\mathcal{A}_{1}\). Note that in this case \(R_{v}\) can contain any subgraph \(H\) with \(\Delta(G)\) nodes. As an example let \(G\) consist of \(H\) and an additional node \(v\) connected to each node of \(H\). A legitimate configuration is given if the state of \(v\) is \(IN\) and all other nodes have state \(OUT\) (Figure 2 left). If \(v\) changes its state to \(OUT\) due to a fault then all nodes may change to state \(IN\) during the next round. Thus, there is little hope for a bound below the trivial bound. Similar arguments hold for the second \(1\)-faulty configuration of \(\mathcal{A}_{1}\) shown on the right of Figure 2.

Figure 1: The numbers indicate the nodes’ colors. If the left-most node is hit by a fault and changes its color to \(\Delta-1\), then itself and its neighbor are enabled. With probability 0.5 the second node changes its color to \(\Delta\). This enables the third node which changes its color to \(\Delta-1\) with probability 0.5. This may causes a cascade of changes in which all nodes on the horizontal line change color. ## 5 Self-Stabilizing Algorithms and Markov Chains

A self-stabilizing algorithm \(\mathcal{A}\) can be regarded as a transition systems of \(\Sigma\). In each round the current configuration \(c\in\Sigma\) is transformed into a new configuration \(\mathcal{A}(c)\in\Sigma\). Each configuration of \(\Sigma\) occurs with a specific probability as the new configuration \(\mathcal{A}(c)\). The source of randomness can have its origin in the scheduler--a probabilistic scheduler randomly selects enabled nodes to make a move--or in a random experiment within one of the rules. We assume that the scheduler and the random experiment are memory-less.