Analyzing the Fault-Containment Time of Self-Stabilizing Algorithms - A Case Study for Graph Coloring

2014/10/24 by Volker Turau, Turau, Volker
Computer Science · #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC

paper · pdf · doi:10.48550/arxiv.1410.6669

23 pages, 5 figures

arxiv created 2014/10/24 · arxiv updated 2014/10/27

Abstract

The paper presents techniques to derive upper bounds for the mean time to recover from a single fault for self-stabilizing algorithms in the message passing model. For a new Delta+1-coloring algorithm we analytically derive a bound for the mean time to recover and show that the variance is bounded by a small constant independent of the network's size. For the class of bounded-independence graphs (e.g. unit disc graphs) all containment metrics are in O(1).

Related

• Computing Fault-Containment Times of Self-Stabilizing Algorithms Using Lumped Markov Chains
• Bounds for self-stabilization in unidirectional networks
• Ressource Efficient Stabilization for Local Tasks despite Unknown Capacity Links
• Communication Efficiency in Self-stabilizing Silent Protocols
• Making Self-Stabilizing any Locally Greedy Problem