About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Information and Computation
Paper
Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement
Abstract
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( n)-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, first shifting into an algorithm of the second family, and finally shifting into an execution of the adaptation of the Dolev, Reischuk, and Strong algorithm. © 1992.