Fault Tolerant Distributed Coloring Algorithms That Stabilize in Linear Time

We propose two new self-stabilizing distributed algorithms for proper Δ+1 (Δ is the maximum degree of a node in the graph) coloring of arbitrary system graphs. Both algorithms are capable of working with multiple types of demons (schedulers) as is the most recent algorithm in [1]. The first algorithm converges in O(m) moves while the second converges in at most n moves (n is the number of nodes and m is the number of edges in the graph) as opposed to the O(Δ×n) moves required by the algorithm [1]. The second improvement is that neither of the proposed algorithms requires each node to have knowledge of Δ, as is required in [1]. Further, the coloring produced by our first algorithm provides an interesting special case of coloring, e.g., Grundy Coloring [2]