Impossibility of distributed consensus with one faulty process

By Michael J. Fischer, Nancy A. Lynch, M. Paterson. 1985

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation (2019, background): “Compared to traditional Byzantine tolerance in distributed systems (Lynch, 1996; Avizienis et al., 2004; Tanenbaum & Van Steen, 2007; Fischer et al., 1982), Byzantine tolerance in distributed machine learning has unique properties and challenges.”
IronFleet: proving practical distributed systems correct (2015, background): “No consensus protocol can be live under arbitrary conditions [16], so this property must be qualified by assumptions.”
A Survey of Distributed Consensus Protocols for Blockchain Networks (2019, background): “[29] that under the asynchronous case, consensus cannot be guaranteed with even a single crash failure.”
Agreeing Asynchronously (2008, background): “” Mathematically the problem is what in statistics and computer science is called a “consensus problem” [3] or an “agreement problem” [4] although in computer science the issues tend to be concerned more with fault tolerance [5] rather than convergence.”
BAR fault tolerance for cooperative services (2005, methodology): “The protocol provides safety (Agreement and Integrity) under an asynchronous model, but guarantees liveness (Termination and Non-Triviality) only during periods of synchrony [24] when there exists a known bound∆ on message delivery time.”
Mencius: Building Efficient Replicated State Machine for WANs (2008, unknown): “Unreliable failure detector Consensus is not solvable in an asynchronous environment when even a single process can fail [14].”
Asynchronous Byzantine Machine Learning (2018, methodology): “…computing literature might note that if asynchrony was possible for Byzantine SGD without restricting the number of successive gradients from a single worker, this could be used as an abstraction to solve asynchronous Byzantine consensus (that is impossible to solve (Fischer et al., 1985)).”
SGD: Decentralized Byzantine Resilience (2019, background): “SMR has been proven to be impossible in asynchronous networks [23], and requires a bound on communication delays between non–Byzantine nodes (at least to hold eventually).”
Bitcoin and Beyond: A Technical Survey on Decentralized Digital Currencies (2016, methodology): “In case of asynchronous communication, the Fischer-Lynch-Paterson (FLP) proof shows that a asynchronous and deterministic consensus protocol cannot tolerate any failures at all [Fischer et al. 1985].”
Secure and Efficient Asynchronous Broadcast Protocols (2001, background): “Often, developers of distributed systems avoid the approach because of the result of Fischer, Lynch, and Paterson [9], which shows that consensus is not reachable by protocols that use an a priori bounded number of steps, even with crash failures only.”
The Next 700 BFT Protocols (2015, background): “In fact, and as our Abstract implementations (ZLight, Quorum, and Chain) exemplify, some Abstract specifications with " weak " Progress can be implemented in the asynchronous model despite Byzantine faults, circumventing the FLP impossibility result [Fischer et al. 1985].”