A Versatile Family of Consensus Protocols Based on Chandra-Toueg's Unreliable Failure Detectors
A Versatile Family of Consensus Protocols Based on Chandra-Toueg's Unreliable Failure Detectors
复制标题
DOI：
10.1109/12.995450
复制
发表时间：
2002-04
期刊：
影响因子：
--
通讯作者：
Michel Hurfin;A. Mostéfaoui;M. Raynal
中科院分区：
文献类型：
--
作者：
Michel Hurfin;A. Mostéfaoui;M. Raynal
本文是关于异步分布式系统的共识协议，易于进程崩溃，但配备了Chandra-Toueg（1996）的不可靠故障检测器。它提出了一个统一的方法，基于两个正交的通用性尺寸。第一个问题涉及底层故障检测器的类别。实例化可以考虑任何类S（假设至少一个进程没有崩溃）或OS（假设大多数进程没有崩溃）的故障检测器。第二个通用性维度涉及在协议的每一轮期间使用的消息交换模式。这种模式（以及因此的轮消息成本）可以为每轮单独定义，从O（n）（集中模式）到O（n/sup 2/）（完全分布式模式），n是进程的数量。由此产生的通用协议具有很好的功能，实际上产生了一个大型的和良好识别的基于故障检测器的共识协议家族。有趣的是，这个家族同时包括新协议和一些众所周知的协议（例如，Chandra-Toueg的基于操作系统的协议）。从方法论的角度来看，这种做法也很有意思。它提供了两组进程的精确表征，在一轮中，必须分别接收要做出的决定（活性）和要决定的单个值（安全性）的消息。有趣的是，该协议的多功能性并不局限于故障检测器：一个简单的基于计时器的实例提供了一个适合部分同步系统的共识协议。
This paper is on consensus protocols for asynchronous distributed systems prone to process crashes, but equipped with Chandra-Toueg's (1996) unreliable failure detectors. It presents a unifying approach based on two orthogonal versatility dimensions. The first concerns the class of the underlying failure detector. An instantiation can consider any failure detector of the class S (provided that at least one process does not crash), or oS (provided that a majority of processes do not crash). The second versatility dimension concerns the message exchange pattern used during each round of the protocol. This pattern (and, consequently, the round message cost) can be defined for each round separately, varying from O(n) (centralized pattern) to O(n/sup 2/) (fully distributed pattern), n being the number of processes. The resulting versatile protocol has nice features and actually gives rise to a large and well-identified family of failure detector-based consensus protocols. Interestingly, this family includes at once new protocols and some well-known protocols (e.g., Chandra-Toueg's oS-based protocol). The approach is also interesting from a methodological point of view. It provides a precise characterization of the two sets of processes that, during a round, have to receive messages for a decision to be taken (liveness) and for a single value to be decided (safety), respectively. Interestingly, the versatility of the protocol is not restricted to failure detectors: a simple timer-based instance provides a consensus protocol suited to partially synchronous systems.