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].