Byzantine Agreement, Broadcast and State Machine Replication with Near-optimal Good-case Latency

This paper investigates the problem \textit{good-case latency} of Byzantine agreement, broadcast and state machine replication in the synchronous authenticated setting. The good-case latency measure captures the time it takes to reach agreement when all non-faulty parties have the same input (or in BB/SMR when the sender/leader is non-faulty). Previous result implies a lower bound showing that any Byzantine agreement or broadcast protocol tolerating more than $n/3$ faults must have a good-case latency of at least $Δ$, where $Δ$ is the assumed maximum message delay bound. Our first result is a family of protocols we call $1Δ$ that have near-optimal good-case latency. We propose a protocol $1Δ$-BA that solves Byzantine agreement in the synchronous and authenticated setting with near-optimal good-case latency of $Δ+2δ$ and optimal resilience $f<n/2$, where $δ$ is the actual (unknown) delay bound. We then extend our protocol and present $1Δ$-BB and $1Δ$-SMR for Byzantine fault tolerant broadcast and state machine replication, respectively, in the same setting and with the same good-case latency of $Δ+2δ$ and $f<n/2$ fault tolerance. Our $1Δ$-SMR upper bound improves the gap between the best current solution, Sync HotStuff, which obtains a good-case latency of $2Δ$ per command and the lower bound of $Δ$ on good-case latency. Finally, we investigate weaker notions of the synchronous setting and show how to adopt the $1Δ$ approach to these models.