Randomized multivalued consensus
Randomized multivalued consensus
复制标题
DOI：
10.1109/isorc.2001.922837
复制
发表时间：
2001-05
期刊：
影响因子：
--
通讯作者：
P. Ezhilchelvan;A. Mostéfaoui;M. Raynal
中科院分区：
文献类型：
--
作者：
P. Ezhilchelvan;A. Mostéfaoui;M. Raynal
一致性问题是在容易发生故障的异步分布式系统上实现可靠服务或应用程序所必须解决的基本问题。不幸的是，在这些系统中，这个问题不能在一个进程崩溃时立即解决(Fischer-Lynch-Paterson的不可能性结果)。已经研究了两种方法来规避这一不可能的结果。两者都在于用适当的“先知”来丰富底层系统。Chandra和Touegg(1996)提出的不可靠故障检测器的概念构成了这类预言的一个家族。自提出以来，基于故障检测器的方法已经产生了几种基于故障检测器的共识协议。Oracle的另一个系列在于允许每个进程使用随机数生成器。在这种情况下，协议终止仅是概率的。针对消息传递的异步分布式系统，已经提出了几种随机化的共识协议。此外，他们认为进程只能从二进制集提出值。本文提出了一种新的随机共识协议，允许进程提出任意值。与其他随机化共识协议相反，该协议不需要进程可以提出的值集合的先验知识。它依赖于随机化和可靠广播的相对简单的组合。
The consensus problem is a fundamental problem one has to solve to implement reliable services or applications on top of asynchronous distributed systems prone to failures. Unfortunately, this problem cannot be solved in those systems as soon as one process crashes (Fischer-Lynch-Paterson's impossibility result). Two approaches have been investigated to circumvent this impossibility result. Both consist in enriching the underlying system with appropriate "oracles". The unreliable failure detector concept proposed by Chandra and Toueg (1996) constitutes one family of such oracles. Since it has been proposed the failure detector based approach has given rise to several failure detector-based consensus protocols. The other family of oracles consists in allowing each process to use a random number generator. In that case, protocol termination is only probabilistic. A few randomized consensus protocols for message-passing asynchronous distributed systems have been proposed. Moreover, they consider that processes can only propose values from a binary set. This paper proposes a new randomized consensus protocol that allows processes to propose arbitrary values. Contrary to other randomized consensus protocols, the proposed protocol does not require the a priori knowledge of the set of values that can be proposed by processes. It relies on a relatively simple combination of randomization and reliable broadcast.