
Self-stabilizing algorithms are a way to deal with network dynamicity, as it will update itself after a network change (addition or removal of nodes or edges), as long as changes are not frequent. We propose an automatic transformation of synchronous distributed algorithms that solve locally greedy and mendable problems into self-stabilizing algorithms in anonymous networks. Mendable problems are a generalization of greedy problems where any partial solution may be transformed -instead of completed- into a global solution: every time we extend the partial solution, we are allowed to change the previous partial solution up to a given distance. Locally here means that to extend a solution for a node, we need to look at a constant distance from it. In order to do this, we propose the first explicit self-stabilizing algorithm computing a (k,k-1)-ruling set (i.e. a "maximal independent set at distance k"). By combining this technique multiple times, we compute a distance-K coloring of the graph. With this coloring we can finally simulate Local model algorithms running in a constant number of rounds, using the colors as unique identifiers. Our algorithms work under the Gouda daemon, similar to the probabilistic daemon: if an event should eventually happen, it will occur.
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Ruling Set, [SCCO.COMP] Cognitive science/Computer science, Self-Stabilizing Algorithm, Distance-K Coloring, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Greedy Problem, Theory of computation → Distributed algorithms, [INFO] Computer Science [cs], 004, ddc: ddc:004
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Ruling Set, [SCCO.COMP] Cognitive science/Computer science, Self-Stabilizing Algorithm, Distance-K Coloring, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Greedy Problem, Theory of computation → Distributed algorithms, [INFO] Computer Science [cs], 004, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
