With an increased need for redundancy and fault tolerance in distributed computing, a 40 years old question is more in focus than ever: how to build a self-replicating distributed fault tolerant system?
Consequences of FLP result
In this second part of the Consensus algorithms blog series, we will quickly go through consequences of FLP result.
There are several variations on the consensus problem that differ in strength. Solution to a stronger consensus problem will typically solve weaker consensus problems at the same time. A strong form of consensus is as follows - given a set of nodes, each with an initial value:
- All non-faulty nodes eventually decide on a value
- All nodes that decide do so on the same value
- The value that has been decided must have been proposed by some node
These three properties are referred to as termination, agreement and validity. Any algorithm that has these three properties can be said to solve the consensus problem. Agreement and validity are safety properties, while termination is referred as a liveness property.
Termination and agreement are fairly explanatory. Please note that we explicitly do not require any particular behaviour from faulty nodes, they are just faulty. Validity is slightly more subtle, although it seems reasonable. The idea behind validity is that we want to exclude trivial solutions that just decide as NO whatever the initial set of values is. Such an algorithm would satisfy termination and agreement but would be entirely of no use at all as it never terminates and never decides the value.
The FLP proof concerns a slightly weaker form of consensus – for termination, it is enough only that some non-faulty node decides. Note that it’s not enough to have one distinguished node that always chooses its value, as that node might fail, and another will have to take its place for even weak termination to be satisfied. Solution to strong consensus will be a perfectly reasonable solution for weak consensus as well, so by ruling out the possibility of the latter, the FLP result similarly precludes a solution to the former.
To quickly sum the FLP result, the basic idea is to show circumstances under which the protocol remains forever indecisive, and consensus cannot be achieved; hence the system will not progress forward. Two steps presented as two separate lemmas are:
- 1st lemma illustrate the existence of an initial condition
- 2nd lemma exploits the result from the first one
They are then tied together to demonstrate the above mentioned idea.
Point 1
The point of the 1st lemma is to show that there is some initial configuration in which the decision is not predetermined, but in fact, it arrived as a result of the sequence of steps taken and the occurrence of any failure.
For example, say that this initial configuration was two nodes whose initial value was ‘0’ and one whose value was ‘1’. The authors show that what is decided from this configuration depends on the order in which messages are received and whether any of the nodes fail, not just what the initial values of the nodes are. This is due to the inherent non-determinism of the asynchronous system model. We call the configurations that may lead to either decision value bivalent, and configurations that will only result in one value 0-valent or 1-valent.
Point 2
The statement of the 2nd lemma says, informally, that if a protocol starts from a bivalent configuration and there is a message e that applies to that configuration, then the set of configurations reachable through any sequence of messages where e is applied last contains a bivalent configuration. More intuitively, the lemma proves that there is a path from a bivalent (read undetermined) configuration to another bivalent (undetermined) configuration, done by delaying a message long enough which raises the possibility that an infinite loop will ensue and the protocol will remain forever undecided.
The impossibility of consensus is thus an important example of the inherent tradeoff between safety and liveness. This is very relevant to consensus algorithms design because it imposes a hard constraint on the problems that we know are solvable in the asynchronous system model.
The safety requirements of consensus are more challenging to meet. Moreover, FLP result did not consider a system with partitions. They were concerned with the more benign issue of crash failures. Explicitly, they assumed that one unknown node could cease operation while most of the nodes in the system continue to communicate reliably. They concluded that consensus is impossible in such a system. In fact, for every purported consensus protocol that guarantees agreement and validity, there is some execution in which there are no failures, and yet the algorithm never terminates.
In the case of a consensus, safety and liveness are impossible if the system is even potentially slightly faulty. This result has had significant implications as the problem of consensus is at the heart of the replicated state machine paradigm, one of the most common approaches for building reliable distributed services (and our middleware problem from the beginning of this article).
The impossibility of fault-tolerant consensus implies that services built according to the replicated state machine paradigm cannot achieve both availability and correctness in an asynchronous network.
In the next blog post in this series, we will see how Paxos and RAFT algorithms address safety and liveness properties, and also, how they work. Stay tuned!
