Exact mean and variance of stabilization time in self-stabilizing graph coloring

The Exact Stabilization Time of Self-Stabilizing Coloring: Mean, Variance, and Distribution

Distributed, Parallel, and Cluster Computing

Summary

When networks fix themselves after errors by recoloring nodes, it usually takes some time to settle. The authors study how long this fixing process takes on average, how much that time varies, and the full probability of all outcomes on different kinds of network shapes. They focus on a classic method where nodes change their colors one by one at random, and they find formulas that depend on the local network structure. This gives a clearer picture than just worst-case time estimates.

What this means in practice

  • For network protocol designers: Predict precise average and variation of recoloring times in self-correcting distributed protocols under random node activations.
  • For distributed system engineers: Optimize system recovery schedules by understanding exact stabilization time distributions for fault-tolerant coloring in network topologies.

Authors

{É}lie de Panafieu, Fabien Mathieu, Maria Gradinariu Potop-Butucaru, S{é}bastien Tixeuil

Abstract

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 the vertices, maxima being taken among the neighbors that share its initial color (the monochrome initial configuration is the slowest case). What can be predicted depends on what is known of the graph. The degree distribution (the view at distance one) gives the mean. The variance needs the view at distance two, in particular the triangles, and the full law needs the whole graph. We give closed-form results, from monochrome and from uniformly random initial configurations, on paths, cycles, random trees, Erdős-R{é}nyi graphs and bipartite random graphs. From a monochrome start, the mean stays within a factor two of the worst case, whereas the variance ranges from zero (disjoint cliques) to order $n^2$ (the star on $n$ vertices)..