Distributed Consensus: Agreement in Faulty Systems

Every time you scan a QR code at a Chennai tea stall and pay through UPI, your bank's core banking server does not act alone. NPCI's switch, your bank's servers, and the merchant's bank's servers are all separate machines, often in separate data centres, and any one of them can crash mid-transaction — power loss, a kernel panic, a network cable pulled during maintenance. Yet the system as a whole must never end up in a state where your ₹40 is deducted from your account but never credited to the tea stall, and never in a state where it is credited twice because a retry fired after a server hiccup. Multiple machines, none of which can be trusted to stay alive, have to agree on a single, unambiguous fact: did this transaction happen, exactly once, and in what order relative to every other transaction touching the same account? That is the distributed consensus problem, and this chapter builds the machinery — quorums, terms, logs, and a hard impossibility result — that makes such agreement possible despite failures.

Stating the problem precisely

A consensus protocol runs across N processes (call them replicas or nodes). Each proposes a value; the protocol must guarantee four properties:

• Agreement — no two correct (non-faulty) replicas decide on different values.
• Validity — the decided value was actually proposed by some replica (no protocol is allowed to just invent an answer).
• Termination — every correct replica eventually decides something; the system does not hang forever.
• Integrity — a replica decides at most once, and cannot un-decide.

Two more variables determine how hard the problem is. First, the failure model: do faulty nodes simply stop (crash faults), or can they send corrupted, contradictory, or actively deceptive messages (Byzantine faults)? Second, the timing model: is the network synchronous, with a known bound on message delay, or asynchronous, where a message can be arbitrarily delayed and you can never distinguish "the node crashed" from "the node is just slow"? UPI-scale banking infrastructure runs over ordinary internet links between data centres — asynchronous, crash-fault territory for the most part, though cross-bank settlement systems that don't fully trust every participant edge into Byzantine territory too. Both cases matter, and this chapter covers both.

Why this is provably hard: the FLP result

In 1985, Michael Fischer, Nancy Lynch, and Michael Paterson proved a result that still governs every distributed system built since: in a fully asynchronous network, no deterministic algorithm can guarantee consensus — agreement, validity, and termination together — if even a single process can crash. The proof doesn't claim consensus is impossible to reach in practice; it claims that an adversary who controls message delivery timing can always construct a schedule that delays the decision forever while never technically violating agreement or validity. The system stays correct but never finishes deciding — termination is the casualty.

This is not a defect that better engineering fixes; it is a theorem. Production systems such as Raft, Paxos, and Zab sidestep it not by disproving it but by giving up the "fully asynchronous, worst-case adversarial schedule" assumption. They assume partial synchrony: message delays are unbounded in theory but in practice settle into a predictable range most of the time, so a replica that hears nothing from a leader for, say, 150–300 milliseconds can safely guess the leader is dead and try to replace it. If the guess is wrong — the leader was merely slow, not dead — the protocol stays safe (it never disagrees) but may briefly stall on liveness (it takes another round to sort itself out). That trade — sacrificing guaranteed termination in pathological cases in exchange for guaranteed safety always — is the standard engineering answer to FLP, and it is exactly what Raft, the algorithm this chapter now works through in detail, does with randomized election timeouts.

The core safety mechanism: majority quorums

Almost every practical crash-fault-tolerant consensus protocol is built on one idea: instead of requiring unanimous agreement from all N replicas, require agreement from any majority — a quorum of size ⌊N/2⌋ + 1. This single design choice is worth deriving carefully, because the entire safety argument for Raft (and Paxos) rests on one small piece of algebra: any two majority quorums drawn from the same N nodes must share at least one common member.

Proof: let A and B be two quorums, each of size m = ⌊N/2⌋ + 1, drawn from a set of N nodes. By inclusion–exclusion, |A ∩ B| = |A| + |B| − |A ∪ B| ≥ |A| + |B| − N, since the union can be at most N. Substituting:

|A ∩ B| ≥ 2(⌊N/2⌋ + 1) − N

For N = 2k+1 (odd):  ⌊N/2⌋ + 1 = k + 1
  |A ∩ B| ≥ 2(k+1) − (2k+1) = 1

For N = 2k (even):    ⌊N/2⌋ + 1 = k + 1
  |A ∩ B| ≥ 2(k+1) − 2k = 2

So for an odd-sized cluster of 5 nodes (the size used throughout this chapter), majority size m = ⌊5/2⌋+1 = 3, and any two majorities overlap in at least 3+3−5 = 1 node. That single guaranteed overlapping node is the entire reason a newly elected leader can never "forget" data that a previous leader already committed — whoever the previous quorum was, the new quorum is forced to include at least one member who witnessed it. Everything else in Raft's safety argument is built on top of this one arithmetic fact.

Worked example: leader election and commit in a 5-node Raft cluster

Take five replicas, A through E, running Raft to replicate a log — think of each log entry as one settled instruction in a ledger, the same role a committed database write plays in a UPI switch.

Term 4 — A is leader. A has appended log entries at indices 1 through 7 and is replicating them via AppendEntries RPCs. B and C are healthy and fast; their replies confirm they have persisted entries up to index 7. D and E are on a slightly congested link and have only caught up to index 6 when the term-4 leader is about to send them entry 7.

A leader in Raft never announces an entry as committed just because it wrote it locally — committing requires a quorum. Concretely, the leader tracks a matchIndex array (the highest log index each follower is known to have replicated) and computes the commit index as the median) of that array once sorted, because that is exactly the largest index acknowledged by a majority:

def commit_index(match_index, quorum):
    ranked = sorted(match_index, reverse=True)
    return ranked[quorum - 1]

# A(self), B, C have index 7; D, E still at index 6
leader_view = [7, 7, 7, 6, 6]
print(commit_index(leader_view, quorum=3))

Trace it by hand: sorted([7,7,7,6,6], reverse=True) is already [7, 7, 7, 6, 6]. Quorum is 3, so we index at position quorum − 1 = 2, which is the third element: 7. The function prints 7. This is the sorted-median trick every Raft implementation uses: the value at position quorum − 1 in the descending-sorted matchIndex array is, by construction, the highest index that at least quorum nodes have acknowledged — because everything at or before that position in the sorted list is ≥ that value. Entry 7 is therefore committed: it has reached A, B, and C, a genuine majority of the 5-node cluster, even though D and E haven't seen it yet.

Partition, then term 5. Now suppose A and B become unreachable — a rack loses network connectivity, a common failure mode in real data centres. C, D, and E each stop hearing heartbeats from A and, after a randomized election timeout, C times out first and starts an election for term 5, requesting votes from D and E.

Here the second half of Raft's safety rule matters: a replica grants its vote only if the candidate's log is at least as up to date as its own (compared first by the term of the last log entry, then by log length). C's log ends at index 7; D and E's logs end at index 6. Since C's log is strictly longer and no less current, D grants its vote, and so does E. C now holds 3 votes (itself, D, E) out of 5 — exactly quorum — and becomes leader for term 5. It immediately replicates entry 7 to D and E, bringing the whole reachable cluster to a consistent state, then continues accepting new writes at index 8 onward.

Notice what did not happen: D and E, despite being a numerical majority of the three reachable nodes, could not have elected a candidate lacking entry 7, because the voting rule would have blocked it. This is the quorum-intersection lemma made concrete — the term-4 commit quorum was {A, B, C}; the term-5 election quorum was {C, D, E}; their intersection is exactly {C}, and C is precisely the node that carries entry 7 forward. If the intersection had been empty, a leader could win an election while being ignorant of already-committed data, and Agreement would be violated. It cannot be empty, because majority quorums out of 5 nodes always overlap in at least one member — that was proved above, not assumed.

Correcting a common misconception

Students who first meet "consensus" as a word, before meeting it as an algorithm, almost always assume it means every replica has to agree before anything is finalized — full unanimity, like a jury verdict. This is wrong, and the error is not cosmetic: a protocol that required all 5 nodes to acknowledge every write would become completely unavailable the instant even one node crashed, since unanimity is then permanently unreachable. That directly collides with Raft's actual guarantee: the system stays live as long as a majority of nodes are up, and it can correctly recognise a commit while a minority is down, slow, or partitioned away. Consensus protocols are built around majority quorums specifically because that is the largest fault tolerance you can buy while still guaranteeing the quorum-intersection property — go smaller than a majority (say, any 2 out of 5) and two disjoint "quorums" of size 2 and 3 could both form without overlapping, and two different leaders could each believe they'd committed different, conflicting entries. Majority is not an arbitrary convention; it is the smallest quorum size for which the overlap proof above holds unconditionally.

When crashing isn't the worst case: Byzantine consensus

Raft and Paxos assume faulty nodes simply go silent. That's realistic for a single company's own replicated database servers, all running the same trusted software. It is not realistic for a settlement network run jointly by competing banks, or a permissioned ledger where a participant might be compromised and start sending different, contradictory messages to different peers — the Byzantine failure model. Byzantine fault tolerance costs strictly more replicas per fault tolerated. Crash-fault Raft needs N = 2f + 1 nodes to survive f crashes (majority quorum, size f+1, always overlaps another majority quorum in at least 1 node, as derived above). Byzantine fault tolerance, as formalized in Castro and Liskov's Practical Byzantine Fault Tolerance (PBFT, 1999), needs N = 3f + 1 nodes and a larger request quorum of size 2f + 1, because a message quorum here must guarantee overlap of at least f + 1 honest nodes, not just 1 — a single honest overlapping node is not enough when the other overlapping members might be actively lying.

Derive the PBFT quorum-overlap bound the same way as before: two quorums of size 2f+1 drawn from N = 3f+1 total nodes overlap in at least 2(2f+1) − (3f+1) = f+1 nodes. Since at most f nodes total are Byzantine-faulty, that overlap of f+1 nodes cannot be entirely faulty — at least one honest node is guaranteed to be in both quorums, and that one honest node is what prevents the system from being tricked into agreeing on two different values. Compare the two systems side by side for a concrete cluster size, N = 13: crash-fault tolerance gives f = ⌊(13−1)/2⌋ = 6 tolerated crashes, while Byzantine tolerance on the same 13 nodes gives only f = ⌊(13−1)/3⌋ = 4 tolerated malicious nodes. Byzantine agreement is strictly more expensive because lying is strictly harder to defend against than silence.

Active recall

Attempt each question before reading its answer.

1. In a 7-node Raft cluster, what is the size of a majority quorum, and how many simultaneous crash failures can the cluster tolerate while still being able to elect a leader?
2. Prove that any two majority quorums drawn from N = 9 nodes must share at least one common node.
3. A Byzantine fault-tolerant cluster is sized at N = 13 to run PBFT. What is the maximum number of Byzantine-faulty nodes f it can tolerate, and what is the required request quorum size?
4. A Raft leader's matchIndex array (including itself) is [12, 12, 11, 11, 9] across 5 nodes, with quorum size 3. What is the commitIndex, and why?
5. In one or two sentences, explain why the FLP impossibility result does not stop Raft from working reliably in production systems.
6. Explain why Raft's rule — "grant your vote only to a candidate whose log is at least as up to date as your own" — is essential for safety, referencing the quorum-intersection argument.

Answers

1. Majority quorum size is ⌊7/2⌋ + 1 = 4. Fault tolerance is f = ⌊(7−1)/2⌋ = 3 crash failures — the cluster can still form a 4-node majority with up to 3 nodes down.

2. Majority size for N = 9 is m = ⌊9/2⌋ + 1 = 5. For two quorums A, B of size 5 each drawn from 9 nodes, |A ∩ B| ≥ |A| + |B| − N = 5 + 5 − 9 = 1. At least one node is shared.

3. PBFT requires N = 3f + 1, so f = ⌊(N−1)/3⌋ = ⌊12/3⌋ = 4. The request quorum size is 2f + 1 = 9. Check: two quorums of 9 out of 13 nodes overlap in at least 9+9−13 = 5 = f+1 nodes, guaranteeing at least one honest node in the overlap since at most 4 are faulty.

4. Sort descending: [12, 12, 11, 11, 9] (already sorted). Index at position quorum − 1 = 2: the value is 11. So commitIndex = 11 — three nodes (positions 0, 1, 2) have replicated at least index 11, which is exactly a majority of 5.

5. FLP proves that no deterministic algorithm can guarantee termination in a fully asynchronous network under an adversarial message schedule with even one crash fault. Raft doesn't defeat this; it assumes partial synchrony (message delays are usually bounded even if not provably so) and uses randomized election timeouts, so it terminates in the timing conditions that hold almost always in real networks, while remaining safe even in the rare cases it doesn't.

6. A term-5 election quorum is guaranteed, by the intersection lemma, to share at least one node with any prior term's commit quorum. Without the up-to-date-log voting rule, that shared node could still vote for a candidate with a shorter, stale log, letting an under-informed node become leader and silently drop already-committed entries — violating Agreement. The voting rule forces the shared node to withhold its vote from any candidate that doesn't already carry the committed history, so the winning candidate is guaranteed to have it.

Think About It

Think about this: How would you explain distributed consensus: agreement in faulty systems to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind distributed consensus: agreement in faulty systems, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.