Fast Byzantine consensus
Reading group: Minh Tung Nguyen presented "Fast Byzantine consensus" (IEEE Transactions on Dependable and Secure Computing) at 1A312 the 19/1/2024 at 10h25.
Abstract
We present the first protocol that reaches asynchronous Byzantine consensus in two communication steps in the common case. We prove that our protocol is optimal in terms of both number of communication steps, and number of processes for two-step consensus. The protocol can be used to build a replicated state machine that requires only three communication steps per request in the common case. Further, we show a parameterized version of the protocol that is safe despite f Byzantine failures and in the common case guarantees two-step execution despite some number t of failures (t ≤ f). We show that this parameterized two-step consensus protocol is also optimal in terms of both number of communication steps, and number of processes.
