Impossibility of distributed consensus with one faulty process
Citation: Micheal J. Fisher, Nancy A. Lynch, Micheal S. Patterson (1985/04) Impossibility of distributed consensus with one faulty process. Journal of the ACM (RSS)
DOI (original publisher): 10.1145/3149.214121
Semantic Scholar (metadata): 10.1145/3149.214121
Sci-Hub (fulltext): 10.1145/3149.214121
Internet Archive Scholar (search for fulltext): Impossibility of distributed consensus with one faulty process
Tagged: Computer Science (RSS) distributed systems (RSS)
One cannot build a consensus protocol with termination, agreement (all nodes to the same value), and validity (the value is one of the initial proposals). See this summary for more.
Theoretical and Practical Relevance
This paper proves a fundamental limitation on asynchronous distributed systems. In practice, the probability of non-termination can be made arbitrarily small, but never zero. Future work would strengthen the assumptions of asynchronous systems to provide properties like consensus and fault-tolerance.