Optimal algorithms for Byzantine agreement
Optimal algorithms for Byzantine agreement
复制标题
DOI：
10.1145/62212.62225
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
Paul Feldman;S. Micali
中科院分区：
文献类型：
--
作者：
Paul Feldman;S. Micali
我们展示了随机的拜占庭一致性（BA）算法，可实现对文献中所考虑的所有类型的对手的最佳运行时间和容错性。我们的BA算法不需要值得信赖的各方，预处理或非构造性参数。给定私人通信线，我们表明，如果在异步网络中发生任何N/3故障，则N处理器可以在同步网络中预期的恒定时间到达BA，如果同步网络和异步网络都无法保证的任何N/4故障发生任何N/4个故障私人通信，我们可能会使用加密术来获得对对手的最佳算法和运行时间的最佳算法。 （因此，在这种情况下，即使在异步网络中，我们也可以忍受多达N/3的故障。）
We exhibit randomized Byzantine agreement (BA) algorithms achieving optimal running time and fault tolerance against all types of adversaries ever considered in the literature. Our BA algorithms do not require trusted parties, preprocessing, or non-constructive arguments. Given private communication lines, we show that n processors can reach BA in expected constant time in a syncronous network if any n/3 faults occur in an asynchronous network if any n/4 faults occur For both synchronous and asynchronous networks whose lines do not guarantee private communication, we may use cryptography to obtain algorithms optimal both in fault tolerance and running time against computationally bounded adversaries. (Thus, in this setting, we tolerate up to n/3 faults even in an asynchronous network.)