Analyzing the Fault-Containment Time of Self-Stabilizing Algorithms - A Case Study for Graph Coloring
Turau, Volker
Original · EN
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).
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.