FLP Impossibility

Researchers have found many different solutions to the consensus problem, but they have also found important constraints that impose some limitations on the possible solutions.

We should note that it’s beneficial to know the limits of the available solutions to a problem, and the research community has benefited massively from this.

We will start by first explaining these limitations and then discussing one solution to the problem. In this way, we will understand the problem better and be better equipped to reason about the solution.

FLP impossibility theory

There are several different system models, with the asynchronous one being the closest to real-life distributed systems. So, it’s proven that in asynchronous systems, where there can be at least one faulty node, any possible consensus algorithm will be unable to terminate under some scenarios. In other words, there can be no consensus algorithm that will always satisfy all the aforementioned properties. This is referred to as the FLP impossibility named after the last initials of the authors of the associated paperM. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of Distributed Consensus with One Faulty Process,” Journal of the ACM (JACM), 1985..

The proof in the paper is quite complicated, but it’s essentially based on the following two parts.

• The fact that it’s always possible that the system’s initial state is one where nodes can reach different decisions depending on the ordering of messages (the so-called bivalent configuration), as long as there can be at least one faulty node
• From such a state, it’s always possible to end up in another bivalent state, just by introducing delays in some messages

As a result, it’s impossible to develop a consensus algorithm that can always terminate successfully in asynchronous systems where at least one failure is possible.

What we can do instead is develop algorithms that minimize this possibility of arriving at ambivalent situations.