Brian A. Coan and Jennifer L. Welch

This paper presents a new Byzantine agreement protocol that tolerates t processor faults using O(t log t) processors, t+1 rounds, O(t^2 + o*t) total message bits (where o is the number of processors that must decide), and messages of maximum size 1 bit. It is the first Byzantine agreement protocol that is simultaneously optimal in rounds, message bits, and message size. The new Byzantine agreemnt protocol is actually a protocol for the (slightly) more general Byzantine relay problem -- a problem which we formulate in this paper. The Byzantine relay protocol is the result of a general recursive construction. Each step of the construction combines two smaller (in terms of number of faults tolerated) Byzantine relay protocols into one larger Byzantine relay protocol. The base case is a collection of very simple Byzantine relay protocols, each tolerant of a small constant number of processor faults. A key new feature of the protocol construction technique presented in this paper is that it does not add unproductive overhead rounds: given two constituent protocols that are optimal in the number of rounds, the composite protocol that is constructed is also optimal in the number of rounds.