论文标题
使任何本地贪婪的问题自我稳定
Making Self-Stabilizing any Locally Greedy Problem
论文作者
论文摘要
我们提出了一种将同步分布式算法转换为匿名网络中的自动化算法的同步分布式算法。可修复的问题是贪婪问题的概括，在这些问题中，任何部分解决方案都可以（而不是完成）变成一个全局解决方案：每次我们扩展部分解决方案时，我们都可以将先前的部分解决方案更改为给定距离。在这里，在这里意味着要扩展节点的解决方案，我们需要查看与该节点的恒定距离。为此，我们提出了第一个明确的自动化算法计算$（k，k-1）$ - 统治集（即“距离$ k $的最大独立集”）。通过将多个时间组合到此技术，我们计算了图形的距离$ k $。借助这种着色，我们最终可以使用颜色作为唯一标识符模拟\ local〜模型算法以恒定数量的弹奏。我们的算法在Gouda守护程序下起作用，这与概率守护程序相似：如果最终应该发生事件，则将发生在此守护程序下。
We propose a way to transform synchronous distributed algorithms solving 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 multiple time this technique, 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, which is similar to the probabilistic daemon: if an event should eventually happen, it will occur under this daemon.
