Good-case Latency of Byzantine Broadcast: A Complete Categorization

Conference Paper

This paper explores the good-case latency of Byzantine fault-tolerant broadcast, motivated by the real-world latency and performance of practical state machine replication protocols. The good-case latency measures the time it takes for all non-faulty parties to commit when the designated broadcaster is non-faulty. We provide a complete characterization of tight bounds on good-case latency, in the authenticated setting under synchrony, partial synchrony and asynchrony. Some of our new results may be surprising, e.g., 2-round PBFT-style partially synchronous Byzantine broadcast is possible if and only if n ≥ 5ƒ-1, and a tight bound for good-case latency under n/3 < ƒ < n/2 under synchrony is not an integer multiple of the delay bound.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • July 21, 2021

Published In

  • Proceedings of the Annual Acm Symposium on Principles of Distributed Computing

Start / End Page

  • 331 - 341

International Standard Book Number 13 (ISBN-13)

  • 9781450385480

Digital Object Identifier (DOI)

  • 10.1145/3465084.3467899

Citation Source

  • Scopus