k-stabilization of reactive tasks
k-stabilization of reactive tasks
复制标题
反应性任务的 k 稳定性
DOI：
10.1145/277697.277777
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
S. Kutten
中科院分区：
文献类型：
--
作者：
J. Beauquier;C. Genolini;S. Kutten
直观地讲，传统的容错方法本质上是全局性的。例如，重置方法（例如[1,2,31]）是将所有节点带入某种预定义状态。这种方法在现代网络中变得越来越不合理，因为现代网络比传统网络大得多，并且增长迅速。因此，[4]中提出，如果故障数量越少，恢复时间越短，协议就可以扩展以处理更大的网络。此类协议称为故障本地[6]。在[4,5,6]中，展示了如何针对各种非反应性问题的情况做到这一点。我们研究了这样的场景：瞬态故障通过不可检测地破坏反应性异步分布式系统中的 k 个（对于给定的 k）个节点来破坏它们的状态。 （节点的确切数量、故障发生的具体节点以及故障发生的时间（如果有的话）都是未知的。）我们专注于反应式系统令牌传递的标准基准问题，并且我们处理更现实的情况，其中持有令牌的节点 P 必须在转发令牌之前完成某些任务（通常称为其程序的关键部分，这是我们算法之外的部分）。因此，没有其他节点可以猜测 P 持有令牌的持续时间。我们提出了两种稳定为合法配置的算法（其中恰好有一个节点具有
Intuitively speaking, traditional fault tolerance methods were global in nature. For example, the reset approach (e.g. [l, 2, 31) is to bring all the nodes into some predefined state. Such an approach is becoming less and less reasonable in modern networks, since these are much larger than traditional ones, and are growing fast. Thus it was suggested in [4] that protocols can scale to handle larger networks if the smaller is the number of faults, the shorter is the recovery time. Such protocols are called fault local [6]. In [4,5,6] it is shown how to do that for various cases of non-reactive problems We study the scenario where transient faults hit up to k (for a given k) nodes in a reactive asynchronous distributed system by corrupting their state undetectably. (The exact number of nodes, the specific nodes the faults hit, and the time they occur, if at all, are not known.) We concentrate on the standard benchmark problem for reactive systemstoken passing, and we treat the more realistic case, where a node P that holds the token must finish some task (often termed the critical section of its program, a section that is outside of our algorithm) before forwarding the token. Thus no other node can guess the duration of the time that P holds the token. We present two algorithms that stabilize into a legitimate configuration (in which exactly one node has