An efficient self-stabilizing distance-2 coloring algorithm

The problem of assigning frequencies to processes so as to avoid interference can in many instances be modeled as a graph coloring problem on the processor graph where no two processes that are sufficiently close are assigned the same color. One version of this problem requires that processes within distance two of each other have different colors. This is known as the distance-2 coloring problem.We present a self-stabilizing algorithm for this problem that uses O(logΔ) memory on each node and that stabilizes in O(Δ2m) time steps for any scheduler (synchronous or asynchronous) using at most Δ2+1 colors, where Δ is the maximum degree in the graph and m is the number of edges in the graph. The analysis holds true for both the sequential and distributed adversarial daemon models. This should be compared with the previous best self-stabilizing algorithm for this problem which stabilizes in O(nm) moves under the sequential adversarial daemon and in O(n3m) time steps for the distributed adversarial daemon and which uses O(δilogΔ) memory on each node i, where n is the number of nodes in the graph and δi is the degree of node i.