A self-stabilizing edge-coloring algorithm for general graphs under the distributed daemon model

摘要

Edge-coloring has many applications in distributed systems, including resource allocation and data transfer scheduling. In this paper, we propose a new self-stabilizing algorithm for edge-coloring general graphs with 2Δ - 1 colors, where Δ is the maximum node degree in the system. To the best of our knowledge, the proposed algorithm is the first edge-coloring algorithm that is self-stabilizing under the distributed daemon model. In addition, the worst-case stabilization time of the proposed algorithm under the distributed daemon model is verified to be O(m) steps, where m is the number of edges in the system. This performance in worst-case stabilization time makes our algorithm the most efficient self-stabilizing edge-coloring algorithm for general graphs to date, because the existing self-stabilizing edge-coloring algorithms for general graphs have at best O(Δm) steps as their worst-case stabilization time.