FLPteoremet

FLPteoremet, commonly known as the FLP impossibility result, is a foundational theorem in distributed computing. It shows that in a fully asynchronous distributed system with crash faults, no deterministic algorithm can guarantee consensus or termination.

The theorem applies to a system of n processes that communicate by message passing, where message delays can be arbitrarily long and clocks provide no guarantees. If at most one process may fail by crashing, there is no deterministic protocol that always reaches a single agreed value (for example 0 or 1) in every possible execution. In particular, there exists an execution in which the processes never reach a decision, even though safety (agreement) is never violated.

Key ideas behind the proof involve the notions of valency and bivalent states. A bivalent state is one from which the system could eventually decide on either value, depending on future message deliveries. The FLP proof shows that, in an asynchronous setting with crashes, there exists an infinite execution path that preserves a bivalent state indefinitely, preventing guaranteed termination. This demonstrates the impossibility of deterministic liveness guarantees alongside safety in the stated model.

Impact and extensions: The FLP result does not say that consensus is impossible in practice, but that it cannot be guaranteed deterministically under pure asynchrony with faults. It motivates the use of randomness or additional timing assumptions. This led to randomized algorithms for consensus (where agreement is achieved with high probability) and to models with partial synchrony or timing bounds, which underpin many practical distributed protocols such as Paxos and related systems. The FLP theorem remains a central reference in the study of fault-tolerant distributed computing.