Shifting gears: changing algorithms on the fly to expedite Byzantine agreement
Shifting gears: changing algorithms on the fly to expedite Byzantine agreement
复制标题
换档：动态改变算法以加快达成拜占庭协议
DOI：
10.1145/41840.41844
复制
发表时间：
1987
影响因子：
2.5
通讯作者：
H. Strong
中科院分区：
文献类型：
--
作者：
A. Bar;Danny Dolev;C. Dwork;H. Strong
我们描述了几个新的算法拜占庭协议。第一个是由于Pease，Shostak和Lamport的原始指数时间拜占庭协议算法的简化，并且具有与他们的算法相当的复杂性。然而，它的证明是非常直观的吸引力。然后研究了解决拜占庭协议问题的算法之间的转换技术。我们提出了两个家庭的算法，通过应用移位运算符，我们的第一个算法。这些家族获得了与Coan家族相同的消息长度权衡轮次，但不需要指数局部计算时间（和他的算法的空间）。我们还描述了一个修改的O（/）-弹性算法的拜占庭协议的Dolev，Reischuk，和强。最后，我们得到了一个混合算法，占主导地位的所有其他的，通过开始执行的算法在一个家庭和转移到第二个家庭的算法，最后转移到执行的Dolev，Reischuk，和强算法的适应。0 `IBM T.沃森研究中心，P。0.信箱704，约克敦高地，纽约10598。这项工作是在作者还是博士时进行的。以色列耶路撒冷希伯来大学的学生。tIBM Almaden研究中心，650 Harry Road，圣何塞，CA 95120和以色列耶路撒冷希伯来大学计算机科学系。$IBM Almaden研究中心，650 Harry Road，圣何塞，CA 95120。§ IBM Almaden Research Center，650 Harry Road，圣何塞，CA 95120。
We describe several new algorithms for Byzantine agreement . The first of-these is a simplification of the original exponential-time Byzantine agreement algorithm due to Pease, Shostak, and Lamport, and is of comparable complexity to their algorithm . However, its proof is very intuitively appealing . A technique of shifting between algorithms for solving the Byzantine agreement problem is then studied . We present two families of algorithms obtained by applying a shift operator to our first algorithm . These families obtain the same rounds to message length trade-off as do Coan's families but do not require the exponential local computation time (and space of his algorithms . We also describe a modification of an O(/ )-resilient algorithm for Byzantine agreement of Dolev, Reischuk, and Strong . Finally, we obtain a hybrid algorithm that dominates all our others, by beginning execution of an algorithm in one family and shifting first into an algorithm of the second family and finally shifting into an execution of the adaptation of the Dolev, Reischuk, and Strong algorithm . 0 `IBM T. J. Watson Research Center, P . 0. Box 704, Yorktown Heights, NY 10598. This work was carried out while this author was a Ph .D . student of the Hebrew University, Jerusalem, Israel . tIBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120 and the Computer Science Department, Hebrew University, Jerusalem, Israel . $IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120 . §IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120 .