Byzantine agreement in the full-information model in O( n) rounds

DOI10.1145/1132516.1132543MaRDI QIDQ2931382zbMATH OpenOpenAlexFDO

Authors Michael Ben-Or, Elan Pavlov, Vinod Vaikuntanathan

Publication date 25 November 2014

Published in Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1132516.1132543

zbMATH Keywords

byzantine agreementfull-information model

Mathematics Subject Classification ID

Applications of game theory (91A80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14) Network protocols (68M12)

Recommendations

• Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds
• scientific article; zbMATH DE number 176512
• Sublinear-round Byzantine agreement under corrupt majority
• An O (log n ) expected rounds randomized byzantine generals protocol
• On the round complexity of randomized Byzantine agreement

Cited in

(17)

• Fault-tolerant graph realizations in the congested clique
• From Almost Everywhere to Everywhere: Byzantine Agreement with $\tilde{O}(n^{3/2})$ Bits
• On the round complexity of randomized Byzantine agreement
• Zombies and ghosts: optimal Byzantine agreement in the presence of omission faults
• On the round complexity of randomized Byzantine agreement
• On expected constant-round protocols for Byzantine agreement
• Sublinear-round Byzantine agreement under corrupt majority
• An O (log n ) expected rounds randomized byzantine generals protocol
• On the round complexity of Byzantine agreement without initial set-up
• Lower bound for scalable Byzantine agreement
• Lower bound for scalable Byzantine agreement
• The best of both worlds: Guaranteeing termination in fast randomized Byzantine agreement protocols
• Scalable and secure computation among strangers: message-competitive Byzantine protocols
• Synchronous Byzantine agreement with expected \(O(1)\) rounds, expected \(O(n^2)\) communication, and optimal resilience
• The contest between simplicity and efficiency in asynchronous Byzantine agreement
• Fast asynchronous Byzantine agreement and leader election with full information
• Efficient Byzantine Agreement with Faulty Minority

This page was built for publication: Byzantine agreement in the full-information model in \(O(\log n)\) rounds

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