# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius
The set \(\Sigma\) is equal to the set of all configurations of \(R_{\triangledown}\) reachable from \(c_{0}\). To partition this set let \(d\) be the number of neighbors of \(v\) that have color \(c_{f}\) in \(c_{0}\). Let \(P=\{\Sigma_{0},\ldots,\Sigma_{d}\}\) where \(\Sigma_{j}\) is the subset of \(\Sigma\) where exactly \(d-j\) neighbors of \(v\) are in conflict with \(v\). Then \(\Sigma_{0}=\{c_{0}\}\) and \(\Sigma_{d}\subseteq\mathcal{L}\). Figure 5 shows some configurations belonging to the sets \(\Sigma_{0}\), \(\Sigma_{2}\), and \(\Sigma_{3}\). Let \(c\in\Sigma_{i}\). Then \(\mathcal{A}_{3}(c)\
ot\in\Sigma_{j}\) for all \(j<i\). Unfortunately the partition \(P\) is not lumpable because the probability of a configuration \(c\in\Sigma_{i}\) to be transformed in one round into a fixed configuration of \(\Sigma_{j}\) is not independent of the choice of \(c\in\Sigma_{i}\). But even in these cases Theorem 1 can lead to an upper bound of the stabilization time. This is proved in the following theorem. Let \(\mathcal{A}\) be a self-stabilizing algorithm with \(\Sigma\) the set of configurations. Let \(P=\{\Sigma_{0},\ldots,\Sigma_{l}\}\) be a partition of \(\Sigma\) with \(\Sigma_{0}=\mathcal{L}\) such that for all \(i\geq 0\) if \(c\in\Sigma_{i}\) then \(\mathcal{A}(c)\in\Sigma_{j}\) with \(j\geq i\). For \(i<j\) let \(c_{ij}\geq 0\) be a constant such that \(Prob(\mathcal{A}(c)\in\Sigma_{j})\geq c_{ij}\) for all \(c\in\Sigma_{i}\). Furthermore, let \(c_{ij}=0\) for \(j<i\) and \(c_{ii}=1-\sum_{j=i+1}^{d}c_{ij}\) for \(i=0,\ldots,d\). Let \(\mathcal{C}^{\mathcal{A}}\) be the Markov chain with states \(P\) and transition matrix \(\big{(}c_{ij}\big{)}\). If an absorbing state of \(\mathcal{C}^{\mathcal{A}}\) is reached from \(\Sigma_{i}\) in expected \(B\) steps then the expected number of rounds \(\mathcal{A}\) requires to stabilize starting in any \(c\in\Sigma_{i}\) is at most \(B\). Proof. : Note

\[0\leq\sum_{j=i}^{d}c_{ij}\leq\sum_{j=i}^{d}Prob(\mathcal{A}_{3}(c)\in\Sigma_{ j})=1\]

for each fixed \(c\in\Sigma_{i}\). Thus, \(c_{ii}\geq 0\) and therefore the matrix \((c_{ij})\) is a stochastic with \(c_{dd}=1\) that describes the new Markov chain \(\mathcal{C}^{\mathcal{A}}\). Remember that \(\mathcal{C}_{\mathcal{A}}\) denotes the markov chain corresponding to algorithm \(\mathcal{A}\). The difference between \(\mathcal{C}_{\mathcal{A}}\) and \(\mathcal{C}^{\mathcal{A}}\) is that with chain \(\mathcal{C}^{\mathcal{A}}\) a node remains with a higher

Figure 4: A 1-faulty configuration \(c_{0}\) for algorithm \(\mathcal{A}_{3}\) where node \(v\) was hit by a fault changing its color to \(c_{f}\) causing a conflict. The corresponding graph \(R_{\triangledown}\) is depicted at the right side. Figure 5: Elements of the partition of \(\Sigma\) for a 1-faulty configuration of algorithm \(\mathcal{A}_{3}\) as described above. \(\Sigma_{0}\) consists of legitimate configurations only. probability in its current configuration instead of moving to a state \(\Sigma_{i}\) with lower index. Therefore, the expected number of steps of \(\mathcal{C}^{\mathcal{A}}\) before being absorbed is an upper bound for the corresponding number in \(\mathcal{C}_{\mathcal{A}}\). The choice of the probabilities implies that \(\mathcal{C}^{\mathcal{A}}\) is lumpable for partition \(P\). Hence, we can apply Theorem 1 to complete the proof. In the rest of this paper the introduced techniques including Theorem 2 are exemplary applied to a self-stabilizing \((\Delta+1)\)-coloring algorithm \(\mathcal{A}_{col}\) using the message passing model. ## 6 Algorithm \(\mathcal{A}_{col}\)

This section introduces coloring algorithm \(\mathcal{A}_{col}\) (see Algorithm 4). Computing a \(\Delta+1\)-coloring in expected \(O(\log n)\) rounds with a randomized algorithm is long known [22; 23]. Algorithm \(\mathcal{A}_{col}\) follows the pattern sketched in Section 4.1. We derived it from an existing algorithm (Algorithm 19 [24]) by adding the self-stabilization property.