Impossibility of distributed consensus with one faulty process

From AcaWiki
Jump to: navigation, search

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
Download: https://dl.acm.org/doi/abs/10.1145/3149.214121
Tagged: Computer Science (RSS) distributed systems (RSS)

Summary

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.

Retrieved from "https://acawiki.org/index.php?title=Impossibility_of_distributed_consensus_with_one_faulty_process&oldid=11962"