Leader-Based Consensus
Leader-Based Consensus
复制标题
DOI：
10.1142/s0129626401000452
复制
发表时间：
2001-03
期刊：
影响因子：
--
通讯作者：
A. Mostéfaoui;M. Raynal
中科院分区：
文献类型：
--
作者：
A. Mostéfaoui;M. Raynal
现在大家都认识到，要在不可靠的、容易发生故障的异步分布式系统上实现可靠的应用程序，共识是必须解决的一个基本问题。已经证明，如果底层异步系统不满足附加假设，则无法解决此问题。本文提出了一种新的基于leader oracle的共识协议（文献中表示为Ω）。尽管该协议使用异步轮询，但它不是基于旋转协调器范例。因此，它不会受到明确使用这种范式的基于招收的共识协议固有的缺点的影响。由于Ω和招收S是等效的，提议的协议不需要比招收S中抽象的假设更强或更弱的假设。因此，它还要求f < n/2（其中n是进程数，f是可能崩溃的进程数的上界）。从设计的角度来看，提议的协议非常简单。从效率的角度来看，当oracle为进程提供相同的leader（实践中常见的情况）时，它允许进程在单个回合中达成一致。当f < n/3时，可以减少协议的时间和消息开销。此外，当系统中除了领导者oracle之外，还配备了随机oracle时，所提出的协议可以扩展为提供混合共识协议，而无需额外的消息开销。
It is now well recognized that consensus is a fundamental problem one has to solve to implement reliable applications on top of unreliable asynchronous distributed systems prone to failures. It has been shown that this problem cannot be solved if the underlying asynchronous system does not satisfy additional assumptions. This paper presents a new consensus protocol based on a leader oracle (denoted Ω in the litterature). Although this protocol uses asynchronous rounds, it is not based on the rotating coordinator paradigm. As a consequence, it does not suffer from drawbacks inherent to ♢S-based consensus protocols that explicity use this paradigm. As Ω and ♢S are equivalent, the proposed protocol does not require assumptions stronger or weaker than the ones abstracted in ♢S. Hence, it also requires f < n/2 (where n is the number of processes and f an upper bound on the number of processes that may crash). From a design point of view, the proposed protocol is surprisingly simple. From an efficiency point of view, it allows the processes to agree in a single round when the oracle provides the processes with the same leader (a common case in practice). It is also shown that the time and message costs of the protocol can be reduced when f < n/3. Moreover, when, in addition to the leader oracle, the system is equipped with a random oracle, the proposed protocol can be extended to provide a hybrid consensus protocol at no additional message cost.