2026-07-22T06:49:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13125 2024-03-06T10:51:37Z ddc:004 open_access

Brief Announcement: Byzantine Agreement, Broadcast and State Machine Replication with Optimal Good-Case Latency Abraham, Ittai Nayak, Kartik Ren, Ling Xiang, Zhuolun Byzantine broadcast synchrony latency state machine replication 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ittai Abraham and Kartik Nayak and Ling Ren and Zhuolun Xiang 2020 Is Part Of LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2020.47 urn:nbn:de:0030-drops-131259 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.47 eng https://creativecommons.org/licenses/by/3.0/legalcode