{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-13","reactions":{}}