{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T23:49:32Z","timestamp":1770680972283,"version":"3.49.0"},"reference-count":25,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2018,5,3]],"date-time":"2018-05-03T00:00:00Z","timestamp":1525305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The analysis of self-stabilizing algorithms is often limited to the worst case stabilization time starting from an arbitrary state, i.e., a state resulting from a sequence of faults. Considering the fact that these algorithms are intended to provide fault tolerance in the long run, this is not the most relevant metric. A common situation is that a running system is an a legitimate state when hit by a single fault. This event has a much higher probability than multiple concurrent faults. Therefore, the worst case time to recover from a single fault is more relevant than the recovery time from a large number of faults. This paper presents techniques to derive upper bounds for the mean time to recover from a single fault for self-stabilizing algorithms based on Markov chains in combination with lumping. To illustrate the applicability of the techniques they are applied to a new self-stabilizing coloring algorithm.<\/jats:p>","DOI":"10.3390\/a11050058","type":"journal-article","created":{"date-parts":[[2018,5,3]],"date-time":"2018-05-03T03:20:27Z","timestamp":1525317627000},"page":"58","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9964-8816","authenticated-orcid":false,"given":"Volker","family":"Turau","sequence":"first","affiliation":[{"name":"Institute of Telematics, Hamburg University of Technology, 21073 Hamburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,5,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/311531.311532","article-title":"Fundamentals of Fault-tolerant Distributed Computing in Asynchronous Environments","volume":"31","year":"1999","journal-title":"ACM Comput. Surv."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Dolev, S. (2000). Self-Stabilization, MIT Press.","DOI":"10.7551\/mitpress\/6156.001.0001"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Azar, Y., Kutten, S., and Patt-Shamir, B. (2010). Distributed Error Confinement. ACM Trans. Algorithms, 6.","DOI":"10.1145\/1798596.1798601"},{"key":"ref_4","first-page":"396","article-title":"Adaptive Stabilization of Reactive Protocols","volume":"Volume 3328","author":"Kutten","year":"2004","journal-title":"Lecture Notes in Computer Science, Proceedings of the International Conference on Foundations of Software Technology and Theoretical Computer Science, Chennai, India, 16\u201318 December 2004"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1006\/jpdc.2001.1824","article-title":"Scalable Self-Stabilization","volume":"62","author":"Ghosh","year":"2002","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1109\/TPDS.2011.158","article-title":"Bounding the Impact of Unbounded Attacks in Stabilization","volume":"23","author":"Dubois","year":"2012","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Delaet, S., and Haddad, S. (2006, January 25\u201329). Necessary and sufficient conditions for 1-adaptivity. Proceedings of the 20th International Parallel and Distributed Processing Symposium, Rhodes Island, Greece.","DOI":"10.1109\/IPDPS.2006.1639331"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s00446-007-0032-2","article-title":"Fault-containing self-stabilizing distributed protocols","volume":"20","author":"Ghosh","year":"2007","journal-title":"Distrib. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s00446-011-0155-3","article-title":"Fault-containing self-stabilization in asynchronous systems with constant fault-gap","volume":"25","author":"Turau","year":"2012","journal-title":"Distrib. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(96)00121-4","article-title":"An exercise in fault-containment: Self-stabilizing leader election","volume":"59","author":"Ghosh","year":"1996","journal-title":"Inf. Process. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"4361","DOI":"10.1016\/j.tcs.2010.11.010","article-title":"A fault-containing self-stabilizing (3 \u2012 2\/(Delta+1))-approximation algorithm for vertex cover in anonymous networks","volume":"412","author":"Turau","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_12","unstructured":"Kemeny, J.G., and Snell, J.L. (1976). Finite Markov Chains, Springer."},{"key":"ref_13","first-page":"240","article-title":"Randomized Finite-state Distributed Algorithms As Markov Chains","volume":"Volume 2180","author":"Duflot","year":"2001","journal-title":"Lecture Notes in Computer Science, Proceedings of the International Symposium on Distributed Computing, Lisbon, Portugal, 3\u20135 October 2001"},{"key":"ref_14","first-page":"224","article-title":"Stability of Distributed Algorithms in the Face of Incessant Faults","volume":"Volume 5873","author":"DeVille","year":"2009","journal-title":"Lecture Notes in Computer Science, Proceedings of the Symposium on Self-Stabilizing Systems, Lyon, France, 3\u20136 November 2009"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s00446-005-0142-7","article-title":"Coupling and Self-Stabilization","volume":"18","author":"Fribourg","year":"2006","journal-title":"Distrib. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Yamashita, M. (December, January 30). Probabilistic Self-Stabilization and Random Walks. Proceedings of the 2011 Second International Conference on Computing, Networking and Communications (ICNC), Osaka, Japan.","DOI":"10.1109\/ICNC.2011.11"},{"key":"ref_17","unstructured":"Mitton, N., Fleury, E., Gu\u00e9rin-Lassous, I., S\u00e9ricola, B., and Tixeuil, S. (2006). On Fast Randomized Colorings in Sensor Networks. Proceedings of ICPADS;, IEEE."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Crouzen, P., Hahn, E., Hermanns, H., Dhama, A., Theel, O., Wimmer, R., Braitling, B., and Becker, B. (2011, January 20\u201324). Bounded Fairness for Probabilistic Distributed Algorithms. Proceedings of the 11th International Conference on Application of Concurrency to System Design (ACSD), Newcastle Upon Tyne, UK.","DOI":"10.1109\/ACSD.2011.21"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Peleg, D. (2000). Distributed Computing: A Locality-Sensitive Approach, SIAM Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898719772"},{"key":"ref_20","unstructured":"Gradinariu, M., and Tixeuil, S. (2000, January 20\u201322). Self-stabilizing Vertex Coloring of Arbitrary Graphs. Proceedings of the 4th International Conference on on Principles of Distributed Systems (OPODIS 2000), Paris, France."},{"key":"ref_21","first-page":"1","article-title":"Superstabilizing Protocols for Dynamic Distributed Systems","volume":"4","author":"Dolev","year":"1997","journal-title":"Chic. J. Theor. Comput. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","article-title":"A Simple Parallel Algorithm for the Maximal Independent Set Problem","volume":"15","author":"Luby","year":"1986","journal-title":"SIAM J. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0020-0190(99)00064-2","article-title":"Simple Distributed \u03b4 + 1-coloring of Graphs","volume":"70","author":"Johansson","year":"1999","journal-title":"Inf. Process. Lett."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Barenboim, L., and Elkin, M. (2013). Distributed Graph Coloring: Fundamentals and Recent Developments, Morgan & Claypool Publishers.","DOI":"10.1007\/978-3-031-02009-4"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Suomela, J., and Wattenhofer, R. (2009, January 3\u20136). Local algorithms: Self-stabilization on speed. Proceedings of the Symposium on Self-Stabilizing Systems, Lyon, France.","DOI":"10.1007\/978-3-642-05118-0_2"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/5\/58\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:03:00Z","timestamp":1760194980000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/5\/58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,3]]},"references-count":25,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2018,5]]}},"alternative-id":["a11050058"],"URL":"https:\/\/doi.org\/10.3390\/a11050058","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,3]]}}}