Asynchronous time-adaptive self stabilization
Asynchronous time-adaptive self stabilization
复制标题
异步时间自适应自稳定
DOI：
10.1145/277697.277778
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
B. Patt
中科院分区：
文献类型：
--
作者：
S. Kutten;B. Patt
我们认为协议，可以承受statecorrupting故障任意翻转的易失性存储器中的位在一个系统中。从协议开始执行（在被破坏的节点处具有任意状态）到系统达到“法律的”状态所经过的时间称为稳定时间。如果系统能从任意暂态破坏性故障中恢复，则称为自稳定[3]。经典的自稳定协议被设计为最小化最坏情况下的稳定时间，而不管有多少节点的状态被损坏的故障。最近，人们已经认识到，如果故障只击中几个处理器，那么更快的稳定是可能的[4，2，51。特别地，在[5]中，如果系统的稳定时间与其状态被破坏的节点的数量成比例，则系统被称为时间自适应或故障局部。状态破坏故障的一个基本问题是持久位的问题[6，51：如何在面对状态破坏时保持单个位的值。形式上，问题定义如下。每个节点保持一个外部可观察的输出位，它满足下列条件：（1）所有的输出位必须相等，除了可能有一个有限的时间，称为输出稳定时间紧跟着故障;（2）如果给定起始状态下的故障数f满足f < n/2，则输出位的最终公共值等于起始状态中的大多数节点的公共值。在[5]中，我们证明了下面的定理。
We consider protocols which can withstand statecorrupting faults which arbitrarily flip the bits of the volatile memory in a system. The time which elapses since the protocol starts executing (with an arbitrary state at the corrupted nodes) until the system reaches a ‘legal’ state is called the stabilization time. If the system can recover from an arbitrary transient statecorrupting fault, it is called self-stabilizing [3]. Classical self-stabilizing protocols were designed to minimize worst-case stabilization time regardless of the number of nodes whose state was corrupted by the fault. Recently, it has been recognized that if the faults hit only a few processors, then much faster stabilization is possible [4, 2, 51. In particular, in [5] a system is called time-adaptive or fault-local if its stabilization time is proportional to the number of nodes whose state was corrupted. A basic problem for state-corrupting faults is the problem of persistent bit [6, 51: how to maintain the value of a single bit in face of state corruption. Formally, the problem is defined as follows. Each node maintains an externally observable output bit which satisfies the following conditions: (1) All output bits must be equal, except perhaps for a finite time, called output stabilization time immediately following a fault; and (2) If the number of faults f in a given start state satisfies f < n/2, then the eventual common value of the output bits is equal to the common value of the majority of the nodes in the start state. In [5], we have proved the following theorem.