Grokking the Principles and Practices of Advanced System Design/

...

/

FLP Impossibility

FLP Impossibility

Learn if consensus is possible in an asynchronous model when nodes can crash.

We'll cover the following...

Due to the Two Generals’ Problem, we have established that we can't guarantee consensus if our network can drop messages, even under the friendly settings of the synchronous computational model. Due to FL82, we also saw that consensus is possible under a synchronous model when the network is non-faulty, but nodes can show crash-stop failures. The next question is: Is consensus possible in an asynchronous setting where a network is assumed to be non-faulty but nodes can exhibit crash stop failures? Unfortunately, it’s not possible due to a result called FLPThe acronym FLP comes from the last name initials of the three authors of this impossibility result—Impossibility of Distributed Consensus With One Faulty Process: Michael Fisher, Nancy Lynch, and Michael Paterson. This same result is also referred to as FLP85 in the research community. impossibility. We’ll understand what the FLP impossibility is in the rest of this lesson.

The FLP impossibility is a crucial result in distributed systems. It addresses whether a deterministic consensus algorithm can satisfy agreement, validity, termination, and fault tolerance in an asynchronous distributed system. However, the FLP theorem suggests that it is impossible to implement consensus algorithms that tolerate even a single node fault.

This result can be counterintuitive and confusing, considering the widespread use of consensus algorithms such as Paxos, Raft, and Zookeeper in large distributed systems where node failures are common.

Understanding the FLP impossibility theorem

Before ...