Communication complexity of Byzantine agreement, revisited

DOI10.1007/S00446-022-00428-8OpenAlexW2916954744MaRDI QIDQ2689834

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

Publication date: 14 March 2023

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-022-00428-8

zbMATH Keywords

lower boundscommunication complexityByzantine agreementsubquadratic

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• On expected constant-round protocols for Byzantine agreement
• Easy impossibility proofs for distributed consensus problems
• Ouroboros Praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain
• A generic approach to constructing and proving verifiable random functions
• Asynchronous Byzantine agreement with subquadratic communication
• Synchronous Byzantine agreement with expected \(O(1)\) rounds, expected \(O(n^2)\) communication, and optimal resilience
• Probabilistic Termination and Composability of Cryptographic Protocols
• Adaptively secure broadcast, revisited
• The Bitcoin Backbone Protocol: Analysis and Applications
• The Hidden Graph Model
• Authenticated Algorithms for Byzantine Agreement
• Adaptively Secure Broadcast
• Scalable leader election
• The Weak Byzantine Generals Problem
• Bounds on information exchange for Byzantine agreement
• The Byzantine Generals Problem
• Breaking the O ( n ² ) bit barrier
• New Techniques for Noninteractive Zero-Knowledge
• Brief Announcement: Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP
• Verifiable random functions from non-interactive witness-indistinguishable proofs

This page was built for publication: Communication complexity of Byzantine agreement, revisited