Self-stabilizing \((\varDelta +1)\) -Coloring in Sublinear (in \(\varDelta \) ) Rounds via Locally-Iterative Algorithms

Fault-tolerance is a central theme in distributed computing. Self-stabilization is a key property that guarantees a distributed system starting from an arbitrary state eventually converges to a desired behavior. Such strong level of fault-tolerance is often desirable due to the error-prone nature of distributed systems. Developing fast and robust coloring algorithms has been a central topic in the study of distributed graph algorithms. In this paper, we give a \((\varDelta +1)\) -coloring algorithm with \(O(\varDelta ^{3/4}\log \varDelta )+\log ^*{n}\) stabilization time, only using messages of size \(O(\log {n})\) , on input graphs of n vertices and maximum degree \(\varDelta \) . This is the first self-stabilizing \((\varDelta +1)\) -coloring algorithm with sublinear-in- \(\varDelta \) stabilization time. The key building block of our algorithm is a new locally-iterative \((\varDelta +1)\) -coloring algorithm with \(O(\varDelta ^{3/4}\log \varDelta )+\log ^*{n}\) runtime. To the best of our knowledge, this is the first locally-iterative \((\varDelta +1)\) -coloring algorithm with sublinear-in- \(\varDelta \) runtime. This answers an open question raised in [Barenboim, Elkin, and Goldberg, JACM ’21].