Communication Complexity of Byzantine Agreement, Revisited

DOI10.1145/3293611.3331629MaRDI QIDQ5145228zbMATH OpenOpenAlexWikidataFDO

Authors Ittai Abraham, T.-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, Elaine Shi

Publication date 20 January 2021

Published in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.03391

zbMATH Keywords

lower boundadaptivecommunication complexityByzantine agreementmulticast

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• Communication complexity of Byzantine agreement, revisited
• Optimally efficient multi-valued byzantine agreement
• Optimal communication complexity of authenticated Byzantine agreement
• Efficient adaptively-secure Byzantine agreement for long messages
• Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party

Cited in

(33)

• How Byzantine is a send corruption?
• On the round complexity of randomized Byzantine agreement
• On the adaptive security of MACs and PRFs
• Rounds in Communication Complexity Revisited
• scientific article; zbMATH DE number 6297761 (Why is no real title available?)
• Completeness theorems for adaptively secure broadcast
• Network-agnostic security comes (almost) for free in DKG and MPC
• Jolteon and Ditto: network-adaptive efficient consensus with asynchronous fallback
• Scalable and secure computation among strangers: message-competitive Byzantine protocols
• Communication complexity of Byzantine agreement, revisited
• Byzantine consensus is \(\Theta(n^2)\): the Dolev-Reischuk bound is tight even in partial synchrony!
• Good-case early-stopping latency of synchronous Byzantine reliable broadcast: the deterministic case
• Sublinear-round Byzantine agreement under corrupt majority
• Non-interactive anonymous router with quasi-linear router computation
• Brief Announcement: Improved Consensus in Quantum Networks
• Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication
• On the Amortized Communication Complexity of Byzantine Broadcast
• On the Validity of Consensus
• Sublinear message bounds of authenticated implicit Byzantine agreement
• Fault-tolerant graph realizations in the congested clique
• Formalizing delayed adaptive corruptions and the security of flooding networks
• Player-replaceability and forensic support are two sides of the same (crypto) coin
• Optimal communication complexity of authenticated Byzantine agreement
• Early stopping for any number of corruptions
• Efficient adaptively-secure Byzantine agreement for long messages
• State machine replication under changing network conditions
• Gossiping for communication-efficient broadcast
• Not a COINcidence: sub-quadratic asynchronous Byzantine agreement WHP
• Round efficient Byzantine agreement from VDFs
• Scalable agreement protocols with optimal optimistic efficiency
• Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party
• Transparent batchable time-lock puzzles and applications to Byzantine consensus
• scientific article; zbMATH DE number 7559107 (Why is no real title available?)

This page was built for publication: Communication Complexity of Byzantine Agreement, Revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145228)