On the Implementation of Unreliable Failure Detectors in Partially Synchronous Systems
On the Implementation of Unreliable Failure Detectors in Partially Synchronous Systems
复制标题
DOI：
10.1109/tc.2004.33
复制
发表时间：
2004-07
期刊：
影响因子：
--
通讯作者：
M. Larrea;Antonio Fernández;S. Arévalo
中科院分区：
文献类型：
--
作者：
M. Larrea;Antonio Fernández;S. Arévalo
Chandra和Toueg提出了不可靠故障检测器，作为提供过程故障信息的机制。Chandra和Toueg定义了八类故障检测器，这取决于这些信息的准确性，并提出了一种算法，实现了这些类中的一个故障检测器的部分同步系统。该算法基于全对全通信，周期性地交换与进程数量成二次关系的消息数量。我们研究了部分同步的几种模型中不同类别的故障检测器的可实现性。我们首先表明，没有故障检测器与永久的准确性（即P，Q，S和W）可以在这些模型中实现，即使是一个单一的故障系统。我们还表明，在这些模型的部分同步，它是必要的大多数正确的过程来实现故障检测器的类/spl θ/Aguilera等人提出的。然后，我们提出了一个家庭的分布式算法，实现了四类不可靠的故障检测器最终的准确性（即，/spl直径/P，/spl直径/Q，/spl直径/S，和/spl直径/W）。我们的算法是基于一个逻辑环安排的过程，它定义了监测和故障信息传播模式。由此产生的算法周期性地交换最多线性数量的消息。
Unreliable failure detectors were proposed by Chandra and Toueg as mechanisms that provide information about process failures. Chandra and Toueg defined eight classes of failure detectors, depending on how accurate this information is, and presented an algorithm implementing a failure detector of one of these classes in a partially synchronous system. This algorithm is based on all-to-all communication and periodically exchanges a number of messages that is quadratic on the number of processes. We study the implementability of different classes of failure detectors in several models of partial synchrony. We first show that no failure detector with perpetual accuracy (namely, P, Q, S, and W) can be implemented in these models in systems with even a single failure. We also show that, in these models of partial synchrony, it is necessary a majority of correct processes to implement a failure detector of the class /spl theta/ proposed by Aguilera et al. Then, we present a family of distributed algorithms that implement the four classes of unreliable failure detectors with eventual accuracy (namely, /spl diams/P, /spl diams/Q, /spl diams/S, and /spl diams/W). Our algorithms are based on a logical ring arrangement of the processes, which defines the monitoring and failure information propagation pattern. The resulting algorithms periodically exchange at most a linear number of messages.