Brief announcement: Byzantine agreement, broadcast and state machine replication with optimal good-case latency

This paper investigates the problem 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) and all messages arrive instantaneously. 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 ∆. Our first result is a matching tight upper bound for a family of protocols we call 1∆. We propose a protocol 1∆-BA that solves Byzantine agreement in the synchronous and authenticated setting with optimal good-case latency of ∆ and optimal resilience f < n/2. 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 optimal good-case latency of ∆ and f < n/2 fault tolerance.