# Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
## 4 Examples
### Contamination Radius
Then

\[E(I,\mathcal{L}) = \sum_{e\in T(I,\mathcal{L})}l(e)p(e)\] \[\epsilon_{i}=(1-a_{1})^{-1}\left(1+\sum_{l=2}^{i}a_{l}\epsilon_{i+1-l}+3a_{i+1} +a_{i+2}\right)\]0 \[\epsilon_{i}=(1-a_{1})^{-1}\left(1+\sum_{l=2}^{i}a_{l}\epsilon_{i+1-l}+3a_{i+1} +a_{i+2}\right)\]1 \[\epsilon_{i}=(1-a_{1})^{-1}\left(1+\sum_{l=2}^{i}a_{l}\epsilon_{i+1-l}+3a_{i+1} +a_{i+2}\right)\]2 \[\epsilon_{i}=(1-a_{1})^{-1}\left(1+\sum_{l=2}^{i}a_{l}\epsilon_{i+1-l}+3a_{i+1} +a_{i+2}\right)\]3 \[\epsilon_{i}=(1-a_{1})^{-1}\left(1+\sum_{l=2}^{i}a_{l}\epsilon_{i+1-l}+3a_{i+1} +a_{i+2}\right)\]4 \[\epsilon_{i}=(1-a_{1})^{-1}\left(1+\sum_{l=2}^{i}a_{l}\epsilon_{i+1-l}+3a_{i+1} +a_{i+2}\right)\]5

The last step uses Lemma 4 and 15. The bound on the variance is proved similarly. Theorem 3.1 and 4.1, Lemma 8 and 16 together prove the following Theorem. Theorem 3.2: \(\mathcal{A}_{col}\) _is a self-stabilizing algorithm for computing a \((\Delta+1)\)-coloring in the synchronous model within \(O(\log n)\) time with high probability. It uses messages of size \(O(\log n)\) and requires \(O(\log n)\) storage per node. With respect to memory and message corruption it has contamination radius \(1\). The expected containment time is at most \(\frac{1}{\ln 2}H_{\Delta_{i}}+11/2\) with variance less than 7.5._

Corollary 1: Algorithm \(\mathcal{A}_{col}\) _has expected containment time \(O(1)\) for bounded-independence graphs. For unit disc graphs this time is at most 8.8._

Proof. : For these graphs \(\Delta_{i}\in O(1)\), in particular \(\Delta_{i}\leq 5\) for unit disc graphs. ## 7 Conclusions

The analysis of self-stabilizing algorithms is often confined to the stabilization time starting from an arbitrary configuration. In practice the time to recover from a 1-faulty configuration is much more relevant. This paper presents techniques to analyze the containment time of randomized self-stabilizing algorithms for 1-faulty configurations. The execution of an algorithm is modeled as a Markov chain, its complexity is reduced with the lumping technique. The power of this technique is demonstrated by an application to a \(\Delta+1\)-coloring algorithm. We believe that the technique can also be applied to other self-stabilizing algorithms. We leave the application to problems such as maximal independents sets and maximal matchings for future work. **Funding:** Research was funded by Deutsche Forschungsgemeinschaft DFG (TU 221/6-2). **Conflicts of Interest:** The author declares no conflict of interest. ## References

* (1) [PERSON] Fundamentals of Fault-tolerant Distributed Computing in Asynchronous Environments. _ACM Comput. Surv._**1999**, _31_, 1-26. [CrossRef]
* (2) [PERSON] _Self-Stabilization_; MIT Press: Cambridge, MA, USA, 2000. * (3) [PERSON]; [PERSON]; [PERSON] Distributed Error Confinement. _ACM Trans. Algorithms_**2010**, _6. [CrossRef]* _[PERSON] (2004)_[PERSON]; [PERSON] Adaptive Stabilization of Reactive Protocols. In _Lecture Notes in Computer Science, Proceedings of the International Conference on Foundations of Software Technology and Theoretical Computer Science, Chennai, India, 16-18 December 2004_; Springer: Berlin/Heidelberg, Germany, 2004; Volume 3328, pp. 396-407. * [PERSON] and [PERSON] (2002) [PERSON]; [PERSON] Scalable Self-Stabilization. _J. Parallel Distrib. Comput._**2002**, _62_, 945-960. [CrossRef]
* [PERSON] et al. (2012) [PERSON]; [PERSON]; [PERSON] [PERSON] Bounding the Impact of Unbounded Attacks in Stabilization. _IEEE Trans. Parallel Distrib. Syst._**2012**, _23_, 460-466. [CrossRef]
* [PERSON] and [PERSON] (2006) [PERSON] [PERSON]; [PERSON] [PERSON]; [PERSON] [PERSON] Necessary and sufficient conditions for 1-adaptivity. In Proceedings of the 20 th International Parallel and Distributed Processing Symposium, Rhodes Island, Greece, 25-29 April 2006; pp. 10-16. * [PERSON] et al. (2007) [PERSON]; [PERSON]; [PERSON]; [PERSON] Fault-containing self-stabilizing distributed protocols. _Distrib. Comput._**2007**, _20_, 53-73.