An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement

DOI10.1137/S0097539790187084zbMath0885.68077WikidataQ56032156 ScholiaQ56032156MaRDI QIDQ4376159

Pesech Feldman, Silvio Micali

Publication date: 10 February 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

randomization; broadcasting; Byzantine agreement; fault-tolerant computation

Mathematics Subject Classification ID

68R05: Combinatorics in computer science

94A60: Cryptography

94A99: Communication, information

68M15: Reliability, testing and fault tolerance of networks and computer systems

94B99: Theory of error-correcting codes and error-detecting codes

68W15: Distributed algorithms

Related Items

Hundreds of impossibility results for distributed computing, Randomized protocols for asynchronous consensus, Cryptography and cryptographic protocols, Resilient-optimal interactive consistency in constant time, Spatial reference frame agreement in quantum networks, Efficient perfectly secure computation with optimal resilience, Efficient perfectly secure computation with optimal resilience, Must the communication graph of MPC protocols be an expander?, Reaching consensus for asynchronous distributed key generation, Fault-tolerant graph realizations in the congested clique, Asymptotically free broadcast in constant expected time via packed VSS, A full proof of the BGW protocol for perfectly secure multiparty computation, Tight bound on mobile Byzantine agreement, On expected constant-round protocols for Byzantine agreement, Perfect information leader election in \(\log^*n+O(1)\) rounds, Perennial secure multi-party computation of universal Turing machine, Round-preserving parallel composition of probabilistic-termination cryptographic protocols, Sublinear-round Byzantine agreement under corrupt majority, How Byzantine is a send corruption?, On the round complexity of randomized Byzantine agreement, Round-optimal Byzantine agreement, Synchronous consensus with optimal asynchronous fallback guarantees, Optimistically tuning synchronous Byzantine consensus: another win for null messages, Asynchronous Byzantine agreement with optimal resilience, Probabilistic termination and composability of cryptographic protocols, Efficient constant-round multi-party computation combining BMR and SPDZ, Lower bound for scalable Byzantine agreement, Improving the round complexity of VSS in point-to-point networks, Algorand: a secure and efficient distributed ledger, Secure multi-party computation made simple, Optimal extension protocols for Byzantine broadcast and agreement, Probabilistic Termination and Composability of Cryptographic Protocols, Secure Message Transmission by Public Discussion: A Brief Survey, Resilient Distributed Field Estimation