Backend
The Exact Stabilization Time of Self-Stabilizing Coloring: Mean, Variance, and Distribution
arXiv cs.DC0 views
arXiv:2611.17989v1 Announce Type: new 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\H{o}s-R{\'e}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)..
Source:https://arxiv.org/abs/2611.17989PreviousTailGuard-GDS: Tail-Safe Control of GPU Storage Data MovementNextZero-SM NCCL: A Systematic Guide to Designing and Deploying SM-Free GPU Communication
Related posts
CoordX Types: A Trustless, Swappable Type System for Shared Records
0arXiv cs.CR
Pairing AIS with RF: Analysis of a Markovian Approach for Maritime Data Fusion
0arXiv cs.CR
Courteous Anticipation: Improving Long-Lived Task Planning in Persistent Shared Environments
0arXiv cs.RO
Foundation Model Driven Robotics: A Comprehensive Review
0arXiv cs.RO
Disturbance-Aware Informative Planning in Spatiotemporal Environments
0arXiv cs.RO

I tore down ai-memory: 528,000 lines of trending code, and you probably don't need it
0dev.to AI