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

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Abraham, I; Nayak, K; Ren, L; Xiang, Z

Published Date

  • October 1, 2020

Published In

Volume / Issue

  • 179 /

International Standard Serial Number (ISSN)

  • 1868-8969

International Standard Book Number 13 (ISBN-13)

  • 9783959771689

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.DISC.2020.47

Citation Source

  • Scopus