Skip to main content

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

Publication ,  Conference
Abraham, I; Nayak, K; Ren, L; Xiang, Z
Published in: Leibniz International Proceedings in Informatics, LIPIcs
October 1, 2020

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.

Duke Scholars

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

ISBN

9783959771689

Publication Date

October 1, 2020

Volume

179

Related Subject Headings

  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Abraham, I., Nayak, K., Ren, L., & Xiang, Z. (2020). Brief announcement: Byzantine agreement, broadcast and state machine replication with optimal good-case latency. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 179). https://doi.org/10.4230/LIPIcs.DISC.2020.47
Abraham, I., K. Nayak, L. Ren, and Z. Xiang. “Brief announcement: Byzantine agreement, broadcast and state machine replication with optimal good-case latency.” In Leibniz International Proceedings in Informatics, LIPIcs, Vol. 179, 2020. https://doi.org/10.4230/LIPIcs.DISC.2020.47.
Abraham I, Nayak K, Ren L, Xiang Z. Brief announcement: Byzantine agreement, broadcast and state machine replication with optimal good-case latency. In: Leibniz International Proceedings in Informatics, LIPIcs. 2020.
Abraham, I., et al. “Brief announcement: Byzantine agreement, broadcast and state machine replication with optimal good-case latency.” Leibniz International Proceedings in Informatics, LIPIcs, vol. 179, 2020. Scopus, doi:10.4230/LIPIcs.DISC.2020.47.
Abraham I, Nayak K, Ren L, Xiang Z. Brief announcement: Byzantine agreement, broadcast and state machine replication with optimal good-case latency. Leibniz International Proceedings in Informatics, LIPIcs. 2020.

Published In

Leibniz International Proceedings in Informatics, LIPIcs

DOI

ISSN

1868-8969

ISBN

9783959771689

Publication Date

October 1, 2020

Volume

179

Related Subject Headings

  • 46 Information and computing sciences