Id: arxiv/2611.17989 Url: https://arxiv.org/abs/2611.17989 Tags: cs.DC, math.CO, math.PR Score: 0 Title: The Exact Stabilization Time of Self-Stabilizing Coloring: Mean, Variance, and Distribution Domain: cs.DC Source: arxiv Authors: {É}lie de Panafieu, Fabien Mathieu, Maria Gradinariu Potop-Butucaru, S{é}bastien Tixeuil Reviews: 0 Subject: cs.DC Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-13 Page: https://delphi.science/r/arxiv/2611.17989 The worst-case stabilization time of a self-stabilizing algorithm usually says little about its typical behavior beyond the order of magnitude. This paper revisits the classical self-stabilizing $Delta+1$ coloring algorithm with vertices activated at random, one at a time (the random central daemon). Considering the number of color changes as a random variable, we study its mean, variance and, on several families of graphs, its exact distribution. The analysis rests on a reduction: a vertex changes color, at most once, exactly when it is not a local maximum of a uniformly random labeling of…