Randomized Byzantine Agreements
Randomized Byzantine Agreements
复制标题
随机拜占庭协议
DOI：
--
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
S. Toueg
中科院分区：
文献类型：
--
作者：
S. Toueg
最近在[Rabi 83]中提出了达到拜占庭协议的随机算法。利用这些算法，在期望的相位数内达成一致，该相位数是独立于过程的数量<italic>n</italic>和故障过程的数量<italic>t</italic>的小常数。[Rabi 83]中的算法在异步系统中最多容忍[（<italic>n</italic>-1）/10]个故障进程，在同步系统中最多容忍[（<italic>n</italic>-1）/4]个故障进程.在本文中，使用相同的计算模型，在[Rabi 83]中，我们描述的算法，克服多达[（<italic>n</italic>-1）/3]故障进程在异步系统中，和多达[（<italic>n</italic>-1）/2]故障进程在同步系统中。对于这两种算法，在预期的相位数内达成一致，该相位数是一个独立于<italic>n</italic>和<italic>t的</italic>小常数，但通信复杂度高于[Rabi 83]。在异步认证系统中，没有一个拜占庭协议算法能克服超过[（<italic>n</italic>-1）/3]个错误进程，因此本文提出的异步协议算法在这方面是最优的.
Randomized algorithms for reaching Byzantine Agreement were recently proposed in [Rabi83]. With these algorithms, agreement is reached within an expected number of phases that is a small constant independent of the number of processes <italic>n</italic> and the number of faulty processes <italic>t</italic>. The algorithms in [Rabi83] tolerate up to [(<italic>n</italic>-1)/10] faulty processes in asynchronous systems, and up to [(<italic>n</italic>-1)/4] faulty processes in synchronous systems. In this paper, using the same computation model as in [Rabi83], we describe algorithms that overcome up to [(<italic>n</italic>-1)/3] faulty processes in asynchronous systems, and up to [(<italic>n</italic>-1)/2] faulty processes in synchronous systems. With both proposed algorithms, agreement is reached within an expected number of phases that is a small constant independent of <italic>n</italic> and <italic>t</italic>, but the communication complexity is higher than in [Rabi83]. It is also shown that no Byzantine Agreement algorithm can overcome more than [(<italic>n</italic>-1)/3] faulty processes in asynchronous authenticated systems, and hence the asynchronous algorithm proposed here is optimal in this respect.