Optimal algorithms for Byzantine agreement
By Paul Feldman, Silvio Micali. 1988
We exhibit randomized Byzantine agreement (BA) algorithms achieving optimal running time and fault tolerance against all types of adversaries ever considered in the literature. Our BA algorithms do not require trusted parties, preprocessing, or non-constructive arguments. Given private communication lines, we show that n processors can reach BA in expected constant time in a syncronous network if any < n/3 faults occur in an asynchronous network if any < n/4 faults occur For both synchronous and asynchronous networks whose lines do not guarantee private communication, we may use cryptography to obtain algorithms optimal both in fault tolerance and running time against computationally bounded adversaries. (Thus, in this setting, we tolerate up to n/3 faults even in an asynchronous network.)
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Dan Alistarh
- Jerry Zheng Li
- Zeyuan Allen-Zhu
- Peter Richtárik
- Ethan Buchman
- Sebastian U. Stich
- Sai Praneeth Karimireddy
- Cong Xie
Citations in the corpus
- Byzantine Stochastic Gradient Descent (2018, methodology): “Our results are presented in the master-worker distribution model, but can be generalized to a coordinator-free distributed setting using standard techniques [12], assuming authenticated point-to-point channels.”
- Secure Multiparty Computation (2011, unknown): “Unfortunately, the impossibility results in Byzantine agreement [11] imply that fairness is not achievable in two-party computation (e.”
- Tendermint: Byzantine Fault Tolerance in the Age of Blockchains (2016, methodology): “The solution was iteratively improved to achieve optimal Byzantine agreement with low overhead [35, 16, 13].”