Self-Stabilization by Local Checking and Global Reset (Extended Abstract)
Self-Stabilization by Local Checking and Global Reset (Extended Abstract)
复制标题
通过局部检查和全局重置实现自稳定（扩展摘要）
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
S. Dolev
中科院分区：
文献类型：
--
作者：
B. Awerbuch;B. Patt;G. Varghese;S. Dolev
我们描述了一种将异步网络协议转换为能够承受任何瞬时故障的协议，即变得自稳定的方法。我们将已知的局部检查概念与内部重置的新概念相结合，证明了给定任何自稳定的内部重置协议，任何可局部检查的协议都可以使其自稳定。我们的证明是建设性的，因为我们提供了显式代码。该方法适用于许多实际网络问题，包括生成树构建、拓扑更新和虚电路设置。
We describe a method for transforming asynchronous network protocols into protocols that can sustain any transient fault, i.e., become self-stabilizing. We combine the known notion of local checking with a new notion of internal reset, and prove that given any self-stabilizing internal reset protocol, any locally-checkable protocol can be made self-stabilizing. Our proof is constructive in the sense that we provide explicit code. The method applies to many practical network problems, including spanning tree construction, topology update, and virtual circuit setup.