Optimal Communication Complexity of Byzantine Consensus under Honest Majority
share
Communication complexity is one of the most important efficiency metrics for distributed algorithms, but considerable gaps in the communication complexity still exist for Byzantine consensus, one of the most fundamental problems in distributed computing. This paper provides three results that help close some of these gaps. (1) We present a Byzantine consistent broadcast (BCB) protocol with linear communication complexity when f ≤ (1/2 - ε)n where ε is any positive constant. The new protocol relies on an expander graph and a threshold signature scheme. (2) The linear BCB protocol is used to obtain quadratic Byzantine broadcast (BB) and Byzantine agreement (BA) under the same f ≤ (1/2 - ε)n resilience (which is close to optimal for BA). (3) We also show a quadratic communication lower bound of BCB with f ≥ (1/2 + ε)n.
READ FULL TEXT