FLP Impossibility

The FLP (Fischer, Lynch, and Paterson) Impossibility theorem is a fundamental theorem in distributed system consensus. It states: “In an asynchronous system, it is impossible to design a deterministic consensus algorithm that can satisfy agreement, termination, and fault tolerance.”

Before we go further into the FLP impossibility theorem, let’s quickly recap consensus and its properties.

A recap of consensus

Consensus in a distributed system is the mechanism in which distributed processes or hosts agree on a particular decision. In a distributed environment with multiple hosts, reliability is a core requirement in the presence of network failures. Therefore, various hosts coordinate together to perform an action that requires the coordinating hosts to agree on some data value:

• Agreement (Safety): All the running hosts should agree on the same value or outcome.

• Termination (Liveliness): Every running host that hasn’t crashed should eventually decide some value.

• Fault tolerance: All the hosts require that a protocol must also be effective in case of node failures.

Asynchronous model vs. synchronous model

In an asynchronous communication model, the message propagation delay from one host to another is unbounded. If a host doesn’t receive the message, it cannot decide whether it was because the other host crashed or got delayed.

In a synchronous communication model, message propagation delays are bounded and host crashes can be reliably detected through timeouts.

FLP theorem