Modular construction of nearly optimal Byzantine agreement protocols

For any > 0, there is a Bysantine agreement protocol that tolerates t processor faults using St + 1 processors, t + O(t) rounds, O(t2+s) total message bits, and local computation polynomial in t. It is optimal or near optimal in all cost measures. The number of processors is optimal. The message bit complexity improves on the previously known upper bound of O(t3 log t) and is close to the known lower bound of (t2). The number of rounds exceeds the lower bound by o(t). The protocol can be compared with the recent result of Moses and Waarts as follows: it uses half as many processors, a factor of O(t6-) fewer message bits, but o(t) more rounds. The new protocol is constructed by recursively applying a simple, yet general, transformation that changes the rounds and total message bits required by a Bysantine agreement protocol, but preserves correctness, number of processor faults tolerated, and total number of processors.

Modular construction of nearly optimal Byzantine agreement protocols Conference Paper