In this topic, we have seen several examples of things that are easy when you have only a single node but that get a lot harder if you want fault tolerance:
-
A database can be linearizable if you have only a single leader and you make all reads and writes on that leader. But how do you fail over if that leader fails, while avoiding split brain? How do you ensure that a node that believes itself to be the leader hasn’t actually been voted out while it’s temporarily paused?
-
A linearizable ID generator on a single node is just a counter with an atomic fetch-and-add instruction—what if it crashes?
-
An atomic CAS operation is useful for deciding who gets a lock or lease when several processes are racing to acquire it, for example, or for ensuring the uniqueness of a file or user with a given name. On a single node, CAS may be as simple as one CPU instruction, but how do you make it fault-tolerant?
It turns out that all of these are instances of the same fundamental distributed systems problem: consensus. The standard formulation of consensus involves getting multiple nodes to agree on a single value. It is one of the most important and fundamental problems in distributed computing; it is also infamously difficult to get right, and many systems have gotten it wrong in the past. Now that we have discussed replication, transactions, system models, and linearizability (this topic), we are finally ready to tackle the consensus problem.
The best-known consensus algorithms are Viewstamped Replication, Paxos, Raft, and Zab. These algorithms have quite a few similarities, but they are not the same. They all work in a non-Byzantine system model—that is, network communication may be arbitrarily delayed or dropped, and nodes may crash, restart, and become disconnected, but the algorithms assume that nodes otherwise follow the protocol correctly and do not behave maliciously.
There are also consensus algorithms that can tolerate some Byzantine nodes (i.e., nodes that don’t correctly follow the protocol—for example, by sending contradictory messages to other nodes). A common assumption is that fewer than one-third of the nodes are Byzantine-faulty. Such algorithms are used in blockchains, for example. However, as explained in “Byzantine Faults”, Byzantine fault-tolerant algorithms are beyond the scope of these notes.