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

Dreame X50 Ultra: designing a Shopify buying journey around fit, bundles and payment conditions
0dev.to JavaScript
Connect Four in 86 lines: how I coded the rules for a multiplayer browser game
0dev.to JavaScript
From Prompt to Production: Architectural Deep‑Dive into MIT’s “How to Make Almost Anything” Framework
0dev.to Rust
PRISM: Preference-based Reward and Uncertainty-Integrated Synthesis Minimization for RTL PPA Optimization
0arXiv cs.SE
The $\alpha$-Limit Problem: Convergence of a Linear Degenerate Interface Transmission Problem
0arXiv cs.NA
A Spectral Proximal DC Algorithm with Nonmonotone Line Search and Extrapolation
0arXiv cs.NA