“Impossibility of Distributed Consensus with One Faulty Process,” by Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson, appeared in the Journal of the Association for Computing Machinery (Volume 32, Number 2, April 1985). It is universally known by the initials of its three authors as the FLP paper.
The paper studies the consensus problem in its starkest form: a set of asynchronous processes, each starting with a binary input, must all decide on the same value, and that value must be one that some process proposed. The authors prove that no completely asynchronous deterministic protocol can guarantee both agreement and termination when even one process may stop. The proof works by constructing an infinite execution in which the system never reaches a decision, exploiting the fact that a slow process and a dead one are indistinguishable.
What makes the result so influential is how little it assumes. The model allows reliable message delivery and only a single crash fault, yet consensus still cannot be guaranteed. This shows the obstacle is timing uncertainty itself, not unreliable networks or malicious behavior.
The work received the PODC Influential Paper Award, later renamed the Edsger W. Dijkstra Prize in Distributed Computing, recognizing it as a foundational result. Every modern consensus algorithm, from Paxos to Raft, is in effect a careful way of adding the timing assumptions that FLP proved are necessary to make agreement reachable.