Fast and compact self-stabilizing verification, computation, and fault detection of an MST
Fast and compact self-stabilizing verification, computation, and fault detection of an MST
复制标题
MST 的快速、紧凑的自稳定验证、计算和故障检测
DOI：
10.1007/s00446-015-0242-y
复制
发表时间：
2015
影响因子：
1.3
通讯作者：
Toshimitsu Masuzawa
中科院分区：
文献类型：
--
作者：
Amos Korman;Shay Kutten;Toshimitsu Masuzawa
本文证明了分布式本地验证的证明，作为一种工具，设计的自稳定算法的有用性。特别是，它引入了一个有点广义的分布式局部证明的概念，并利用它来显着提高时间复杂度，同时保持空间最优性。其结果是，我们表明，优化内存大小进行最小的成本在时间方面，在最小生成树（MST）的上下文中。也就是说，我们提出的算法，都是时间和空间有效的构造MST和验证它。这涉及到几个部分，可以被认为是在自己的贡献。首先，我们推广了局部证明的概念，权衡了时间复杂度和内存效率。这增加了一个维度的分布式本地证明，这已获得关注最近的研究。具体地说，我们设计了一个（自稳定）证明标记方案，它是记忆最优的（即，bits per node），其时间复杂度在同步网络中为，在异步网络中为，其中为节点的最大度。这回答了Awerbuch et al.（1991）提出的一个开放性问题。我们还表明，时间是必要的，即使在同步网络。另一个性质是，如果发生了故障，那么，在上述要求的检测时间内，它们被每个故障所在地的某个节点检测到。其次，我们展示了如何增强一个已知的Transformer，使输入/输出算法自稳定。它现在将一个有效的构造算法和一个有效的自稳定证明标记方案作为输入，并产生一个有效的自稳定算法。当用于MST时，Transformer产生了一个内存最优自稳定算法，其时间复杂度，即，甚至比以前的算法（以前的MST算法的时间复杂度为，使用每个节点的内存位，和最优空间算法的时间）有明显的改善。继承于我们的证明标记方案，我们的自稳定MST构造算法还具有以下两个性质：（1）如果故障发生在构造结束后，则它们在同步网络中的时间内或异步网络中的时间内被一些节点检测到;（2）如果故障发生，则在上述所需的检测时间内，它们在每个故障的局部性内被检测到。我们还展示了如何提高上述两个属性，在内存的一些增加的代价。
This paper demonstrates the usefulness of distributed local verification of proofs, as a tool for the design of self-stabilizing algorithms. In particular, it introduces a somewhat generalized notion of distributed local proofs, and utilizes it for improving the time complexity significantly, while maintaining space optimality. As a result, we show that optimizing the memory size carries at most a small cost in terms of time, in the context of minimum spanning tree (MST). That is, we present algorithms that are both time and space efficient for both constructing an MST and for verifying it. This involves several parts that may be considered contributions in themselves. First, we generalize the notion of local proofs, trading off the time complexity for memory efficiency. This adds a dimension to the study of distributed local proofs, which has been gaining attention recently. Specifically, we design a (self-stabilizing) proof labeling scheme which is memory optimal (i.e.,bits per node), and whose time complexity isin synchronous networks, ortime in asynchronous ones, whereis the maximum degree of nodes. This answers an open problem posed by Awerbuch et al. (1991). We also show thattime is necessary, even in synchronous networks. Another property is that iffaults occurred, then, within the required detection time above, they are detected by some node in thelocality of each of the faults. Second, we show how to enhance a known transformer that makes input/output algorithms self-stabilizing. It now takes as input an efficient construction algorithm and an efficient self-stabilizing proof labeling scheme, and produces an efficient self-stabilizing algorithm. When used for MST, the transformer produces a memory optimal self-stabilizing algorithm, whose time complexity, namely,, is significantly better even than that of previous algorithms (the time complexity of previous MST algorithms that usedmemory bits per node was, and the time for optimal space algorithms was). Inherited from our proof labeling scheme, our self-stabilising MST construction algorithm also has the following two properties: (1) if faults occur after the construction ended, then they are detected by some nodes withintime in synchronous networks, or withintime in asynchronous ones, and (2) iffaults occurred, then, within the required detection time above, they are detected within thelocality of each of the faults. We also show how to improve the above two properties, at the expense of some increase in the memory.