Consensus can be expressed in several ways. For example:
-
Single-value consensus is very similar to an atomic CAS operation. It can be used to implement locks, leases, and uniqueness constraints.
-
Constructing an append-only log also requires consensus, which is usually formalized as total order broadcast. With a log, you can implement state machine replication, leader-based replication, event sourcing, and other useful patterns.
-
An atomic fetch-and-add (or atomic increment) operation also turns out to be equivalent to consensus.
-
Atomic commitment of a multidatabase or multishard transaction requires that all participants agree on whether to commit or abort the transaction.
In fact, these problems are all equivalent. If you have an algorithm that solves one of these problems, you can convert it into a solution for any of the others. This is quite a profound and perhaps surprising insight. It’s also why we can lump all these things together under “consensus,” even though they look quite different on the surface. Let’s take a closer look at each of them to see why this is the case.
Single-value consensus
The ability to get multiple nodes to agree on a single value is very useful. For example:
-
When a database with single-leader replication first starts up, or when the existing leader fails, several nodes may concurrently try to become the leader. Similarly, multiple nodes may race to acquire a lock or lease. Consensus allows them to decide which one wins.
-
If several people concurrently try to book the last seat on an airplane or the same seat in a theater, or try to register an account with the same username, then a consensus algorithm can determine which one should succeed if it’s not clear who got there first.
More generally, one or more nodes may propose values, and the consensus algorithm decides on one of those values. In the examples given here, each node could propose its own ID, and the algorithm would decide which node ID should become the new leader, the holder of the lease, or the buyer of the airplane/theater seat. In this formalism, a consensus algorithm must satisfy the following properties:
Uniform agreement
No two nodes decide differently.
Integrity
After a node has decided one value, it cannot change its mind by deciding another value.
Validity
If a node decides value v, then v was proposed by a node.
Termination
Every node that does not crash eventually decides a value.
If you want to decide multiple values, you can run a separate instance of the consensus algorithm for each. For example, you could have a separate consensus run for each bookable seat in the theater so that you get one decision (one buyer) for each seat.
The uniform agreement and integrity properties define the core idea of consensus: everyone decides on the same outcome, and after you have decided, you cannot change your mind. The validity property rules out trivial solutions—for example, you could have an algorithm that always decides null, no matter what was proposed; this algorithm would satisfy the agreement and integrity properties, but not the validity property.
If you don’t care about fault tolerance, satisfying the first three properties is easy. You can just hardcode one node to be the “dictator,” and let that node make all the decisions. However, if that one node fails, the system can no longer make any decisions—just like single-leader replication without failover. All the difficulty arises from the need for fault tolerance.
The termination property formalizes the idea of fault tolerance. It essentially says that a consensus algorithm cannot simply sit around and do nothing forever—in other words, it must make progress. Even if some nodes fail, the other nodes must still reach a decision. (Termination is a liveness property, whereas the other three are safety properties—see “Distinguishing between safety and liveness”.)
If a crashed node may recover, you could just wait for it to come back. However, a consensus algorithm must ensure that it makes a decision even if a crashed node suddenly disappears and never comes back. (Instead of a software crash, imagine that an earthquake causes the datacenter containing your node to be destroyed by a landslide. You must assume that your node is buried under 30 feet of mud and is never going to come back online.)
Of course, if all nodes crash and none are running, it is not possible for any algorithm to decide anything. There is a limit to the number of failures that an algorithm can tolerate. In fact, it can be proved that any consensus algorithm requires at least a majority of nodes to be functioning correctly in order to assure termination. That majority can safely form a quorum (see “Using quorums for reading and writing”).
Thus, the termination property is subject to the assumption that fewer than half of the nodes are unreachable. However, most consensus algorithms ensure that the safety properties—agreement, integrity, and validity—are always met, even if a majority of nodes fail or a severe network problem occurs. Thus, a large-scale outage can stop the system from being able to process requests, but it cannot corrupt the consensus system by causing it to make inconsistent decisions.
Compare-and-set as consensus
A CAS operation checks whether the current value of an object equals an expected value. If so, it atomically updates the object to a new value; if not, it leaves the object unchanged and returns an error.
If you have a fault-tolerant, linearizable CAS operation, solving the consensus problem is easy. Initially set the object to a null value, then have each node that wants to propose a value perform a CAS, with the expected value being null and the new value being the value it wants to propose (assuming it is non-null). The decided value is then whatever value the object is set to.
Likewise, if you have a solution for consensus, you can implement CAS. Whenever one or more nodes want to perform a CAS with the same expected value, you use the consensus protocol to propose the new values in the CAS invocation and then set the object to whatever value was decided by consensus. Any CAS invocations whose proposed value was not decided return an error. CAS invocations with different expected values use separate runs of the consensus protocol.
This shows that CAS and consensus are equivalent. Again, both are straightforward on a single node but challenging to make fault-tolerant. As an example of CAS in a distributed setting, we saw conditional write operations for object stores in “Databases Backed by Object Storage”, which allow a write to happen only if an object with the same name has not been created or modified by another client since the current client last read it.
Shared logs as consensus
We have seen several examples of logs, such as replication logs, transaction logs, and write-ahead logs. A log stores a sequence of log entries, and anyone who reads it sees the same entries in the same order. Sometimes a log has a single writer that is allowed to append new entries, but a shared log is one where multiple nodes can request that entries be appended. An example is single-leader replication: any client can ask the leader to make a write, which the leader appends to the replication log, and then all followers apply the writes in the same order as the leader.
More formally, a shared log supports two operations: you can request that a value be added to the log, and you can read the entries in the log. It must satisfy the following properties:
Eventual append
If a node requests that a value be added to the log, and the node does not crash, then that node must eventually read that value in a log entry.
Reliable delivery
No log entries are lost—if one node reads a log entry, then eventually every node that does not crash must also read that log entry.
Append-only
After a node has read a log entry, it is immutable, and new log entries can be added only after it, not before. If the node rereads the log, it will see the same log entries in the same order as it read them initially (even if the node crashes and restarts).
Agreement
If two nodes both read a log entry e, then prior to e they must have read exactly the same sequence of log entries in the same order.
Validity
If a node reads a log entry containing a value, then a node previously requested that value’s addition to the log.
Note
A shared log can be implemented using a total order broadcast protocol, also known as atomic broadcast or total order multicast protocol. To add a value to the log, we “broadcast” it using the protocol, and when the protocol “delivers” it, the value becomes part of a log entry that can be read.
If you have an implementation of a shared log, solving the consensus problem is easy. Every node that wants to propose a value requests that it be added to the log, and whichever value is read back in the first log entry is the value that is decided. Since all nodes read log entries in the same order, they are guaranteed to agree on which value is delivered first.
Conversely, if you have a solution for consensus, you can implement a shared log. The details are a bit more complicated, but the basic idea is this:
-
You have a slot in the log for every future log entry, and you run a separate instance of the consensus algorithm for every such slot to decide what value should go in that entry.
-
When a node wants to add a value to the log, it proposes that value for one of the slots that has not yet been decided.
-
When the consensus algorithm decides for one of the slots, and all the previous slots have already been decided, then the decided value is appended as a new log entry, and any consecutive slots that have been decided also have their decided value appended to the log.
-
If a proposed value was not chosen for a slot, the node that wanted to add it retries by proposing it for a later slot.
This shows that consensus is equivalent to total order broadcast and shared logs. Single-leader replication without failover does not meet the liveness requirements since it stops delivering messages if the leader crashes. As usual, the challenge is in performing failover safely and automatically.
Fetch-and-add as consensus
The linearizable ID generator we saw in “Linearizable ID Generators” comes close to solving consensus, but it falls slightly short. We can implement such an ID generator by using a fetch-and-add operation, which atomically increments a counter and returns the old counter value.
If you have a CAS operation, implementing fetch-and-add is easy. First read the counter value, then perform a CAS where the expected value is the value you read, and the new value is that value plus 1. If the CAS fails, you retry the whole process until the CAS succeeds. This is less efficient than a native fetch-and-add operation when there is contention, but it is functionally equivalent. Since you can implement CAS using consensus, you can also implement fetch-and-add using consensus.
Conversely, if you have a fault-tolerant fetch-and-add operation, can you solve the consensus problem? Let’s say you initialize the counter to 0, and every node that wants to propose a value invokes the fetch-and-add operation to increment the counter. Since the fetch-and-add operation is atomic, one node will read the initial value of 0, and all the others will read a value that has been incremented at least once.
Now let’s say that the node that reads 0 is the winner, and its value is decided. That works for the node that read 0, but the other nodes have a problem: they know that they are not the winner, but they don’t know which of the other nodes has won. The winner could send a message to the other nodes to let them know it has won, but what if the winner crashes before it has a chance to send this message? In that case the other nodes are left hanging, unable to decide any value, and thus the consensus does not terminate. And the other nodes can’t fall back to another node because the node that read 0 may yet come back and rightly decide the value it proposed.
An exception occurs if we know for sure that no more than two nodes will propose a value. In that case, the nodes can send each other the values they want to propose and then each perform the fetch-and-add operation. The node that reads 0 decides its own value, and the node that reads 1 decides the other node’s value. This solves the consensus problem for two nodes, which is why we can say that fetch-and-add has a consensus number of 2. In contrast, CAS and shared logs solve consensus for any number of nodes that may propose values, so they have a consensus number of ∞ (infinity).
Atomic commitment as consensus
In “Distributed Transactions” we saw the atomic commitment problem, which is to ensure that the databases or shards involved in a distributed transaction all either commit or abort a transaction. We also saw the two-phase commit algorithm, which relies on a coordinator that is a single point of failure.
What is the relationship between consensus and atomic commitment? At first glance, they seem very similar—both require nodes to come to some form of agreement. However, there is one important difference: with consensus it’s OK to decide any value that was proposed, whereas with atomic commitment the algorithm must abort if any of the participants voted to abort. More precisely, atomic commitment requires the following properties:
Uniform agreement
It is not possible for one node to commit and another to abort.
Integrity
Once a node has committed, it cannot change its mind to abort, and vice versa.
Validity
If a node commits, all nodes must have previously voted to commit. If any node voted to abort, all nodes must abort.
Nontriviality
If all nodes vote to commit, and no communication timeouts occur, then all nodes must commit.
Termination
Every node that does not crash either commits or aborts eventually.
The validity property ensures that a transaction can commit only if all nodes agree, and the nontriviality property ensures that the algorithm can’t simply always abort (but it allows an abort if any of the communication among the nodes times out). The other three properties are basically the same as for consensus.
If you have a solution for consensus, you could solve atomic commitment in multiple ways. One works like this: when you want to commit the transaction, every node sends its vote to commit or abort to every other node. Nodes that receive a vote to commit from themselves and every other node propose “commit” via the consensus algorithm; nodes that receive a vote to abort, or that experience a timeout, propose “abort” via the consensus algorithm. When a node finds out what the consensus algorithm decided, it commits or aborts accordingly.
In this algorithm, “commit” will be proposed only if all nodes voted to commit. If any node voted to abort, all proposals in the consensus algorithm will be “abort.” It could happen that some nodes propose “abort” while others propose “commit” if all nodes voted to commit but some communication timed out; in this case, it doesn’t matter whether the nodes commit or abort, as long as they all do the same thing.
If you have a fault-tolerant atomic commitment protocol, you can also solve consensus. Every node that wants to propose a value starts a transaction on a quorum of nodes, and at each node it performs a single-node CAS to set a register to the proposed value if its value has not already been set by another transaction. If the CAS succeeds, the node votes to commit, and otherwise it votes to abort. If the atomic commit protocol commits a transaction, its value is decided for consensus; if atomic commit aborts, the proposing node retries with a new transaction.
This shows that atomic commit and consensus are also equivalent to each other.