Good-case Latency of Byzantine Broadcast: A Complete Categorization

Ittai Abraham, Kartik Nayak, Ling Ren, Zhuolun Xiang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationPODC 2021 - Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages331-341
Number of pages11
ISBN (Electronic)9781450385480
DOIs
StatePublished - Jul 21 2021
Event40th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2021 - Virtual, Online, Italy
Duration: Jul 26 2021Jul 30 2021

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference40th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2021
Country/TerritoryItaly
CityVirtual, Online
Period7/26/217/30/21

Keywords

  • byzantine broadcast
  • latency
  • optimal

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this