Banner

Planetary Scale Byzantine Consensus

Byzantine fault tolerant consensus protocols are implemented with consecutive broadcasts but suffer from a low throughput at large geographical scale or planetary scale. A reason for this inefficiency is believed to be their all-to-all communication complexity, which led researchers to design new consensus protocols with more consecutive one-to-all broadcasts but cumulatively fewer messages.

Authored by:
Gauthier Voron, Swiss Federal Institute of Technology
Vincent Gramoli, University of Sydney, CTO Redbelly Network

 

Byzantine fault tolerant consensus protocols are implemented with consecutive broadcasts but suffer from a low throughput at large geographical scale or planetary scale. Areas on for this inefficiency is believed to be their all-to-all communication complexity, which led researchers to design new consensus protocols with more consecutive one-to-all broadcasts but cumulatively fewer messages.

We show, through a step-by-step evaluation, ranging from LAN/WAN broadcast benchmarks to a state machine replication (SMR) application, that this intuition can be misleading. In particular, we identify two underestimated factors that can impact consensus performance much more at a large scale: (i) the goodput of the broadcast as the rate at which bits are delivered to the application and (ii) the hiccup or waiting time between consecutive broadcast phases. Finally, we show that a leaderless SMR with 𝑂(𝑛4) complexity can outperform a leader-based SMR with 𝑂(𝑛3) complexity by 20×.

This work promotes a new family of byzantine consensus protocols exclusively based on all-to-all broadcasts that take into account these two factors. Our result promises to impact the design of blockchain systems that aim at performing well in WANs at a planetary scale.

Read the Full Paper

This paper was co-authored by our CTO and Founder Professor Vincent Gramoli.

Professor Vincent Gramoli is a full professor at the University of Sydney. He is a researcher in the field of distributed systems and algorithms, with a focus on the design and analysis of distributed systems and algorithms for shared memory and data-centric systems, including distributed hash tables, distributed shared memory and transactional memory. He has published numerous papers in top-tier conferences and journals in the field and has received several awards for his research. He is also currently serving as the Head of Concurrent Systems Research Group at the University of Sydney.