Communication Complexity of Byzantine Agreement, Revisited

DOI10.1145/3293611.3331629OpenAlexW2962882087MaRDI QIDQ5145228

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

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 boundmulticastcommunication complexityadaptiveByzantine agreement

Mathematics Subject Classification ID

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

Related Items (18)

On the round complexity of randomized Byzantine agreement ⋮ Jolteon and Ditto: network-adaptive efficient consensus with asynchronous fallback ⋮ Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party ⋮ Transparent batchable time-lock puzzles and applications to Byzantine consensus ⋮ Formalizing delayed adaptive corruptions and the security of flooding networks ⋮ Gossiping for communication-efficient broadcast ⋮ Fault-tolerant graph realizations in the congested clique ⋮ Efficient adaptively-secure Byzantine agreement for long messages ⋮ State machine replication under changing network conditions ⋮ Completeness theorems for adaptively secure broadcast ⋮ Network-agnostic security comes (almost) for free in DKG and MPC ⋮ On the Amortized Communication Complexity of Byzantine Broadcast ⋮ Brief Announcement: Improved Consensus in Quantum Networks ⋮ On the Validity of Consensus ⋮ Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication ⋮ On the adaptive security of MACs and PRFs ⋮ Sublinear-round Byzantine agreement under corrupt majority ⋮ How Byzantine is a send corruption?

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