Modular construction of a Byzantine agreement protocol with optimal message bit complexity (Q1186809)

The paper deals with a new Byzantine Agreement Protocol (BAP) whose quality is described by the following measures: --- the number of processors required to tolerate at most \(t\) faults, --- the number of rounds of communication, --- the total number of message bits, --- the size of the largest message. The authors define the general transformation as the composition of two transformations, namely, from BAP to BBP (Byzantine Broadcast Protocol), and from a collection of BBPs to BAP. The new BAP protocol is constructed by recursive applying these transformations. In addition, some theorems which show the higher quality of the proposed BAP, as compared to well known BAPs, are proved. The new BAP turns out to be optimal or near optimal with respect to all quality measures.