The Consensus Problem

Consensus is a coordination problem in which $n$ processes, each starting with a private input value, must collectively agree on a single output value. Formally, every process $p_i$ proposes a value $v_i$ by calling `propose(v_i)`, and every correct process must eventually call `decide(v)` for some value $v$, satisfying three properties.

Agreement: no two correct processes decide on different values. This is the safety property — it says nothing bad ever happens, but permits a system that never decides anything at all (so it cannot stand alone).

Validity (sometimes called non-triviality): the decided value must be one of the proposed values (in the simplest formulation), or more generally must satisfy some application-defined validity predicate over the inputs. Validity rules out trivial protocols that always decide a hard-coded constant, which would satisfy agreement vacuously.

Termination: every correct process eventually decides, in finite time. This is the liveness property — the protocol cannot stall forever waiting for a message that never arrives. A protocol solves consensus for a given failure model if it satisfies all three properties under that model's assumptions. The failure model, inherited from Fault Tolerance and Failure Models, specifies how many of the $n$ processes may fail ($f$) and how they may fail: crash-stop (a process simply halts and sends nothing more), crash-recovery (a process halts and may later resume with persistent state), or Byzantine (a process may send arbitrary, even maliciously crafted, messages). The timing model matters equally: in a synchronous system, message delay and processing time are bounded and known, so a missing message is detectable as a failure; in an asynchronous system, there is no such bound, so a slow message is indistinguishable from a crashed sender. This indistinguishability is the seed of the impossibility results that follow.

Rather than presenting one specific protocol (that is the job of Paxos Consensus Protocol and Raft Consensus Algorithm), we present the generic shape every consensus algorithm takes, and the abstract machinery — rounds, quorums, and proposal numbers — that recurs in essentially all correct solutions. Understanding this shape lets you evaluate any consensus protocol against the same checklist. Most practical consensus protocols proceed in asynchronous rounds, each round attempting to get a majority (or a Byzantine-tolerant supermajority) of processes to agree on a candidate value. A round has two phases: a propose phase, where a coordinator broadcasts a candidate value tagged with a round number, and a quorum phase, where the coordinator waits for acknowledgments from a quorum — a large-enough subset of processes such that any two quorums must overlap. The overlap guarantees that if a value has already been chosen by one quorum, any later quorum will contain at least one process that knows about it, preventing a conflicting decision. ``` // Generic round-based consensus skeleton // n processes, tolerate f failures, quorum size q = floor(n/2) + 1 state at each process p: round := 0 proposedVal := null // value p is currently pushing acceptedVal := null // last value p has accepted acceptedRnd := -1 // round in which acceptedVal was accepted decided := false function propose(v): proposedVal := v while not decided: round := round + 1 // Phase 1: ask a quorum whether round `round` is safe to use, // and learn about any value already partially agreed responses := broadcast_and_collect(PREPARE, round, quorum_size = q) if responses.count < q: continue // no quorum reachable, retry with new round // adopt the highest-numbered previously accepted value, if any highest := argmax(responses, key = r -> r.acceptedRnd) if highest.acceptedVal != null: proposedVal := highest.acceptedVal // Phase 2: ask the quorum to accept (round, proposedVal) accepts := broadcast_and_collect(ACCEPT, round, proposedVal, quorum_size = q) if accepts.count >= q: acceptedVal := proposedVal acceptedRnd := round broadcast(DECIDE, proposedVal) decided := true return proposedVal // else: some other proposer's round pre-empted this one; retry function on_receive(PREPARE, r) at process p: if r > round: round := r reply (acceptedVal, acceptedRnd) else: reply REJECT // a higher round is already in progress function on_receive(ACCEPT, r, v) at process p: if r >= round: round := r acceptedVal := v acceptedRnd := r reply ACK else: reply REJECT ``` This skeleton is deliberately abstract — it is the common ancestor of Paxos-family protocols. Two design choices deserve attention. First, the quorum intersection property: any two quorums of size $q = \lfloor n/2 \rfloor + 1$ out of $n$ processes must share at least one member, since $2q > n$. Second, the adopt-the-highest-round-value rule in Phase 1 is what prevents two different rounds from deciding two different values — a later round is forced to re-propose whatever an earlier round may have already gotten a quorum to accept, even if the later coordinator does not yet know a decision happened.

The remaining piece is termination: the pseudocode above retries with an incremented round whenever a quorum cannot be reached, which is safe (it never violates agreement) but is not guaranteed to terminate if proposers keep interrupting each other's rounds forever — this dueling proposers scenario is precisely why pure asynchronous consensus cannot guarantee both safety and liveness, a fact made rigorous in the FLP Impossibility Result. Practical systems break the tie using a stable leader (via Leader Election) so that, most of the time, only one process is proposing per round.

Message complexity. A single round of the generic protocol requires each of $n$ processes to send to (up to) $n$ others in the prepare phase and again in the accept phase, giving $O(n^2)$ messages per round in the worst case, or $O(n)$ if a stable leader broadcasts directly to all followers and they reply only to the leader (the common case in practice). Since termination is not guaranteed in bounded rounds under full asynchrony, the expected number of rounds under partial synchrony with a correctly-functioning leader is $O(1)$; under adversarial scheduling it is unbounded in theory, though randomized consensus protocols achieve expected $O(1)$ rounds even against an adversary.

Time complexity. Each round costs two message round-trips (prepare, then accept), so a successful decision costs $O(1)$ round-trip times when there is no contention — this is why leader-based protocols like Raft are fast in the common case.

Space complexity. Each process stores $O(1)$ state variables (current round, accepted value, accepted round) in the crash-stop model; in richer protocols (multi-value logs), each process stores $O(k)$ state for $k$ decided log entries, which is unavoidable since the log itself is the output.

Correctness argument for agreement (safety). We sketch why the generic protocol never lets two processes decide different values, by induction on round number. Suppose, for contradiction, two different values $v \neq v'$ are decided in rounds $r < r'$ respectively. Deciding $v$ in round $r$ means a quorum $Q$ accepted $(r, v)$. For round $r'$ to propose $v' \neq v$, its proposer must have run Phase 1 of round $r'$, collecting responses from some quorum $Q'$. By quorum intersection, $Q \cap Q' \neq \emptyset$: pick $p \in Q \cap Q'$. Process $p$ accepted $(r, v)$, so its `acceptedRnd` is at least $r$ and its `acceptedVal` is $v$ (or a value from an even later round $r'' < r'$, by the same argument applied inductively to the highest round below $r'$). The Phase 1 rule requires the proposer of round $r'$ to adopt the value belonging to the highest `acceptedRnd` reported by $Q'$, which is at least $r$ — so the proposer of $r'$ must set `proposedVal` to $v$ (or to whatever the maximal earlier accepted value is, tracing back by strong induction to $v$), contradicting the assumption that $v' \neq v$ was proposed. Hence no two rounds can decide different values, which by transitivity gives agreement across all correct processes. This is exactly the safety proof structure underlying Paxos Consensus Protocol.

Validity follows directly from the construction: `proposedVal` is initialized only from a process's own input or adopted from a previously accepted value, which itself traces back (by induction on rounds) to some process's original input — no value is ever invented out of thin air.

Termination is the honest tradeoff. The FLP Impossibility Result proves that in a fully asynchronous system where even a single process may crash, no deterministic algorithm can guarantee both agreement and termination simultaneously — there always exists some execution (an adversarial message schedule) that keeps the system in an undecided state forever, without ever technically declaring any process "failed" (since failures and slow messages are indistinguishable). This is not a failure of engineering effort; it is a theorem. Real systems sidestep it by strengthening the model: assuming partial synchrony (eventually, message delays are bounded, even if not known in advance), using randomization (Ben-Or's algorithm achieves expected termination via random coin flips), or using failure detectors (an oracle, however imperfect, that eventually suspects crashed processes correctly). Every production consensus protocol you will study next silently relies on one of these three escape hatches.

Consider $n = 5$ processes $\{P_1, \dots, P_5\}$ tolerating $f = 2$ crash failures, quorum size $q = 3$. Suppose $P_1$ proposes value `"commit-tx-42"` and $P_4$ simultaneously proposes `"abort-tx-42"` because of a race in the client layer — a classic dueling-proposer scenario.

Two observations make this trace non-trivial. First, $P_4$'s own proposed value ("abort") was overridden by the protocol rule — this is the mechanism, not a bug, that guarantees agreement even though two different clients proposed conflicting values. Second, $P_1$'s round 1 never fully failed silently: it partially propagated (to $P_3$) and that partial trace is exactly what $P_4$ picked up in step 8, preventing a split decision. Had the adopt-highest-value rule been skipped, $P_4$ could have decided `"abort-tx-42"` while $P_3$ still locally held `"commit-tx-42"` — violating agreement the moment either value were read by a client.

Consensus emerged from very concrete distributed-computing failures — clocks drifting apart, replicated databases diverging, and the recognition that "just wait a bit longer" is not a specification. The formal treatment of the problem, and the proof of its limits, is one of the most cited results in all of computer science.

Consensus is the invisible engine behind almost every system that claims to be "strongly consistent." Distributed databases such as Google Spanner, CockroachDB, and etcd use Paxos- or Raft-family consensus to agree on transaction ordering and replicated log entries. Coordination services like Apache ZooKeeper and etcd (built on Zab and Raft respectively) provide consensus-backed primitives — leader locks, configuration stores, service discovery — that countless microservices depend on for Leader Election. Blockchain systems reframe consensus for open, adversarial networks: Bitcoin's proof-of-work and Byzantine fault-tolerant protocols like PBFT and Tendermint solve consensus among mutually distrusting parties with no central authority, directly extending the Byzantine failure model introduced here. Even mundane infrastructure — distributed locks in cloud storage, multi-datacenter replication in messaging queues, and cluster membership protocols in Kubernetes — all reduce, at their core, to some instance of the same agreement-validity-termination triple defined in this article.

Ask the tutor: How does the "adopt the highest accepted value" rule specifically prevent the split-brain scenario where two leaders each believe they hold a quorum?