FLP impossibility theorem

The FLP impossibility theorem, named after Fischer, Lynch, and Paterson, who proved it in 1985, states that it is impossible to design a totally asynchronous distributed system that can reliably solve the consensus problem in the presence of even one failure.

The consensus problem requires that all processes in a distributed system eventually agree on a single value, given some initial set of proposed values. For example, in BGP, the generals need to reach a consensus on a plan of attack.

The key assumptions in the FLP impossibility proof are as follows:

• Asynchrony: There are no bounds on message delays or process speeds. Processes communicate by sending messages but have no shared clock.
• Process failures: Up to f out of n processes may fail by crashing, where 0 < f < n.
• Finite steps: Processes take a finite number of steps and messages have a finite size.

Under these conditions, the FLP theorem proves that there is no deterministic...