One of the most important results in distributed computing was published in April 1985 by Fischer, Lynch and Paterson. Their short paper “Impossibility of Distributed Consensus with One Faulty Process” definitively placed an upper bound on what it is possible to achieve with distributed processes in an asynchronous environment.
The problem of consensus – that is, getting a distributed network of processes to agree on a common value – was known to be solvable in a synchronous setting, where an arbitrary number of processes might crash. In contrast, the FLP (Fischer, Lynch, and Paterson) theorem shows that in an asynchronous setting, where only one process might crash, there is no distributed algorithm that solves the consensus problem.
In this talk, I will present the proof itself because, although rather short, it is subtle and profound. I’ll start by introducing the consensus problem, and then after describing the computing model, I will work through the various lemmas that make up this proof.
