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.