The problem of Byzantine agreement was originally discussed in the context of synchronous systems[1]} where it was solved using a recursive algorithm with factorial message complexity. Most Byzantine fault tolerant consensus protocols used today have been inspired by PBFT [2]}. PBFT guarantees safety during asynchrony periods but requires synchronous phases to guarantee progress. In PBFT processes use an all-to-all communication scheme which offers, for a small numbers of processes, excellent throughput and latency. However, due to the quadratic message cost it does not scale to large system sizes. Although there have been many proposals to extend and improve several aspects of PBFT (for instance, [3]}, [4]}, [5]}, [6]}) most preserve the same communication pattern.
