TY - GEN
T1 - Improved extension protocols for byzantine broadcast and agreement
AU - Nayak, Kartik
AU - Ren, Ling
AU - Shi, Elaine
AU - Vaidya, Nitin H
AU - Xiang, Zhuolun
N1 - Funding Information:
Funding Kartik Nayak and Ling Ren are supported in part by a VMware early career faculty grant. Elaine Shi: Elaine Shi is supported in part by NSF award 1561209, and part of the work was done when the author was a long-terms visitor in Simons Institute for the “Proofs, Consensus, and Decentralizing Societ” program. Nitin H. Vaidya: Nitin H. Vaidya is supported in part by NSF award 1849599.
Publisher Copyright:
© Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang; licensed under Creative Commons License CC-BY 34th International Symposium on Distributed Computing (DISC 2020).
PY - 2020/10/1
Y1 - 2020/10/1
N2 - Byzantine broadcast (BB) and Byzantine agreement (BA) are two most fundamental problems and essential building blocks in distributed computing, and improving their efficiency is of interest to both theoreticians and practitioners. In this paper, we study extension protocols of BB and BA, i.e., protocols that solve BB/BA with long inputs of l bits using lower costs than l single-bit instances. We present new protocols with improved communication complexity in almost all settings: authenticated BA/BB with t < n/2, authenticated BB with t < (1 − ε)n, unauthenticated BA/BB with t < n/3, and asynchronous reliable broadcast and BA with t < n/3. The new protocols are advantageous and significant in several aspects. First, they achieve the best-possible communication complexity of Θ(nl) for wider ranges of input sizes compared to prior results. Second, the authenticated extension protocols achieve optimal communication complexity given the current best available BB/BA protocols for short messages. Third, to the best of our knowledge, our asynchronous and authenticated protocols in the setting are the first extension protocols in that setting.
AB - Byzantine broadcast (BB) and Byzantine agreement (BA) are two most fundamental problems and essential building blocks in distributed computing, and improving their efficiency is of interest to both theoreticians and practitioners. In this paper, we study extension protocols of BB and BA, i.e., protocols that solve BB/BA with long inputs of l bits using lower costs than l single-bit instances. We present new protocols with improved communication complexity in almost all settings: authenticated BA/BB with t < n/2, authenticated BB with t < (1 − ε)n, unauthenticated BA/BB with t < n/3, and asynchronous reliable broadcast and BA with t < n/3. The new protocols are advantageous and significant in several aspects. First, they achieve the best-possible communication complexity of Θ(nl) for wider ranges of input sizes compared to prior results. Second, the authenticated extension protocols achieve optimal communication complexity given the current best available BB/BA protocols for short messages. Third, to the best of our knowledge, our asynchronous and authenticated protocols in the setting are the first extension protocols in that setting.
KW - Byzantine agreement
KW - Byzantine broadcast
KW - Communication complexity
KW - Extension protocol
UR - http://www.scopus.com/inward/record.url?scp=85106948555&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85106948555&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.DISC.2020.28
DO - 10.4230/LIPIcs.DISC.2020.28
M3 - Conference contribution
AN - SCOPUS:85106948555
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 34th International Symposium on Distributed Computing, DISC 2020
A2 - Attiya, Hagit
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 34th International Symposium on Distributed Computing, DISC 2020
Y2 - 12 October 2020 through 16 October 2020
ER -