Distributed Systems: Consensus & Replication

Every time a UPI transfer clears in under two seconds, a small miracle of coordination has just happened. Your bank's ledger, NPCI's switch, and the receiving bank's ledger are three separate systems, running on separate machines, in separate data centres — and every one of them must end up agreeing that exactly ₹500 left your account and exactly ₹500 arrived in your friend's, never zero, never two transfers, never a transfer that vanishes because one server happened to reboot at the wrong millisecond. Multiply that guarantee across roughly 14 billion transactions a month and you get a sense of the actual engineering problem: not "store the data" but "get multiple independent machines to agree on the data, even when some of them crash, lag, or get cut off from the network mid-decision." That agreement problem has a name — consensus — and the technique of keeping multiple synchronized copies of the same data so that no single machine's failure loses anything is replication. This chapter builds both from first principles, ending with a fully traced worked example of the algorithm that most production consensus systems (etcd, CockroachDB, Kafka's controller, TiKV) actually run: Raft.

Why a single database is never enough

Start with the naive design: one server holds the authoritative copy of every account balance. It is simple, and it is completely wrong for anything that must stay up. Two independent failure modes kill it. First, durability — if that one machine's disk fails between accepting your transfer and confirming it, the transfer is gone, even though the bank already told you "success." Second, availability — if that one machine is down for maintenance, or its data-centre loses power, or a fibre cut isolates it, the entire payment system halts, regardless of how healthy every other machine on Earth is. Neither failure mode is exotic. Data-centre power events, top-of-rack switch failures, and single-disk faults are routine at the scale IRCTC or UPI operate at — with millions of requests per minute, a mean time between hardware failures measured in months means something is failing somewhere almost every day.

The fix seems obvious: keep more than one copy. Replicate the ledger across three, five, or seven machines, ideally spread across different racks or data centres, so that no single fault takes out all copies at once. But the instant you have multiple copies, you have created a new problem that a single machine never had: the copies can disagree. If the primary machine accepts your ₹500 transfer and crashes before telling the backups, does the backup that takes over know about it or not? If two machines each briefly believe they are "the" primary during a network hiccup, and each accepts different, conflicting writes, whose write wins? Replication without a plan for resolving disagreement is not safer than one machine — it is a machine that can produce two contradictory answers to the same question, which for a payment ledger is worse than downtime.

Consensus: getting replicas to agree on one history

Consensus is the general problem: a set of N machines, some of which may crash or become slow or get network-partitioned away from the rest, must agree on a single sequence of values (in our case, a single ordered log of ledger operations) such that every machine that says "this entry is confirmed" is guaranteed never to have to take that confirmation back. The two properties a correct consensus protocol must deliver are usually stated as:

• Agreement (safety) — no two nodes ever confirm conflicting values at the same log position. This must hold no matter how badly the network misbehaves — messages delayed, reordered, or dropped — as long as messages that do arrive are not corrupted.
• Termination (liveness) — as long as a majority of nodes can talk to each other, the system keeps making progress and does not stall forever.

Notice the asymmetry: safety is an absolute, unconditional promise; liveness is conditional on enough of the network working. This is not an accident — it reflects a hard mathematical result. A theorem proved by Fischer, Lynch, and Paterson in 1985 (usually just called "FLP") shows that in a purely asynchronous network — one with no bound on message delay — no deterministic algorithm can guarantee both safety and liveness at the same time if even one node might fail. Real systems route around this by accepting that liveness can pause (the system might briefly stop accepting new writes) while refusing to ever compromise safety (it will never confirm two different values for the same slot). Raft, which we build below, is precisely this kind of algorithm: it can stall during a bad network partition, but it never lies about what it has committed.

Quorums: how many replicas must agree before a write counts

The mechanism that makes this work is the quorum: a write is only considered committed once a majority of the N replicas have durably stored it — not all N, just more than half. For a cluster of N nodes, define:

majority(N) = floor(N / 2) + 1
fault_tolerance(N) = floor((N - 1) / 2)

Work through the numbers, because they explain a design choice you will see in almost every real system (etcd production clusters are commonly run at 5 nodes, ZooKeeper ensembles are almost always odd-sized):

N = 3  ->  majority = 2,  tolerates 1 failure
N = 4  ->  majority = 3,  tolerates 1 failure
N = 5  ->  majority = 3,  tolerates 2 failures
N = 6  ->  majority = 4,  tolerates 2 failures
N = 7  ->  majority = 4,  tolerates 3 failures

Look at N=4 versus N=3: both tolerate exactly one failure, but N=4 needs a larger quorum (3 machines instead of 2) to make progress, and costs an entire extra machine to buy nothing in fault tolerance. The fourth node is dead weight — it raises the quorum bar without raising the failure budget. This is why production consensus clusters are almost always odd-sized: N=5 buys you a full extra failure of tolerance over N=4 for the same one additional node, while N=6 buys you nothing over N=5. The general rule, visible directly in the two formulas above, is that fault tolerance only increases when N crosses from even to the next odd number, never from odd to the next even number.

The reason a majority is sufficient (rather than requiring all N) comes from a simple pigeonhole argument called quorum intersection: any two majorities out of the same N nodes must share at least one common node. If quorum A has majority(N) nodes and quorum B has majority(N) nodes, and the cluster only has N nodes total, then |A| + |B| > N, so A and B cannot be disjoint — they overlap in at least one machine. This single fact is the entire reason distributed consensus is possible without unanimity: whichever majority confirmed a write, any future majority that tries to make a decision — including electing a new leader — is guaranteed to include at least one node that already knows about that write, and can refuse to let it be forgotten.

Raft: leader election and log replication

Raft organizes the N replicas as a replicated log — an append-only sequence of operations (like "x = 1", "credit account 42 by ₹500") that every replica applies in the same order, giving every replica the same resulting state. At any moment exactly one node is the leader; every other node is a follower. Only the leader accepts new client writes. Time is divided into terms — monotonically increasing integers, incremented every time a new leader election happens — which is the mechanism that prevents split-brain: if two nodes both believe they are leader, one of them necessarily has an older term number, and every other node in the cluster will reject that older leader's messages once it has seen the higher term, forcing the stale leader to step down the moment it hears from anyone with a newer term.

Log replication works as follows. The leader appends the new entry to its own log at some index, tagged with its current term, then sends it to every follower via an AppendEntries RPC. Followers append it and reply with an acknowledgement carrying how far their own log now extends — the leader tracks this per follower as matchIndex. An entry becomes committed — safe to apply and safe to report back to the client as durable — only once matchIndex shows that a majority of nodes (leader included) have replicated it, and the entry was created in the leader's current term.

That second condition is not decorative. Suppose a term-1 entry is replicated to a majority, but the leader crashes before it commits any entry of its own current term on top of it. In one classic failure sequence (Raft's own paper documents this as "Figure 8"), a later leader — elected in a higher term — can, while still doing entirely correct AppendEntries replication, end up overwriting that seemingly majority-replicated older-term entry before it is ever safely committed. Raft closes this hole with a strict rule: a leader is only permitted to advance its commit index by directly counting majorities on entries from its own current term; earlier-term entries only become committed indirectly, by riding along underneath a current-term entry that itself gets committed. It's a subtle rule, and it is exactly the kind of edge case that separates a real consensus protocol from something that merely "looks like it agrees" most of the time.

Worked example: tracing commit index on a 5-node cluster

Take a 5-node cluster — nodes A, B, C, D, E — with A as leader in term 1. A client sends three writes; A appends them to its own log as index 1 (x = 1), index 2 (y = 2), index 3 (x = 3), all tagged term 1. A replicates to all four followers, but the network is uneven: B receives and acknowledges all three entries, while C, D, and E — momentarily slower — have only received and acknowledged entry 1 so far. The leader's view of replication progress, one matchIndex value per node including itself, is:

node:        A   B   C   D   E
matchIndex:  3   3   1   1   1

Here is the exact rule the leader runs to compute its commit index, translated into runnable code:

def majority_commit_index(match_index, current_term, log_terms):
    """
    match_index: highest log index each node (leader included) is known
                 to have durably replicated, e.g. [3, 3, 1, 1, 1]
    current_term: the leader's current term number
    log_terms:    term number of the entry AT each index, 1-indexed,
                   so log_terms[0] is the term of log index 1
    Returns the new commit index (0 if nothing new can be committed).
    """
    n = len(match_index)
    majority = n // 2 + 1
    for idx in sorted(set(match_index), reverse=True):
        replicated_count = sum(1 for m in match_index if m >= idx)
        if replicated_count >= majority and log_terms[idx - 1] == current_term:
            return idx
    return 0

match_index = [3, 3, 1, 1, 1]        # A, B, C, D, E
log_terms   = [1, 1, 1]              # entries at index 1, 2, 3 are all term 1
print(majority_commit_index(match_index, current_term=1, log_terms=log_terms))

Trace it by hand before trusting the printed answer. The candidate indices, taken from the distinct values in match_index and checked from highest to lowest, are 3 and then 1. At idx = 3: count how many entries in [3, 3, 1, 1, 1] are ≥ 3 — that's A and B only, a count of 2. Majority for 5 nodes is 5 // 2 + 1 = 3, and 2 is not ≥ 3, so index 3 fails. At idx = 1: count how many entries are ≥ 1 — all five, a count of 5, which is ≥ 3, and log_terms[0] = 1 matches current_term = 1, so the function returns 1. The program prints 1.

That result is the whole point made concrete: even though the leader's own log already holds three entries, only index 1 (x = 1) is safe to report back to the client as durable. Entries 2 and 3 exist on only two of five machines — if A crashed right now, they could vanish from history and no promise was ever broken, because no promise was ever made about them.

Now let the network catch up: C receives and acknowledges entries 2 and 3 as well, updating the leader's table to [3, 3, 3, 1, 1]. Re-run the same function. At idx = 3: count of entries ≥ 3 is now A, B, C — 3 nodes — which meets the majority of 3, and log_terms[2] = 1 matches the current term, so it returns 3. All three entries are now committed in one step, because the third acknowledgement was the one that completed a majority.

What happens if the leader crashes at the first snapshot

Suppose A crashes right after the first snapshot above — matchIndex still [3, 3, 1, 1, 1], commit index still 1. A new election starts in term 2 among the four surviving nodes. Raft's election-safety rule requires every voter to reject a candidate whose log is less up to date than its own (compared first by the term of the last log entry, then by log length). Suppose C is the first to start an election: C's log ends at index 1, term 1. B's log ends at index 3, term 1 — strictly longer at the same term — so B refuses to vote for C. But D and E both also end at index 1, term 1, identical to C's log, and Raft's rule treats a tie as "at least as up to date," so D and E are permitted to vote for C. C collects votes from itself, D, and E — three votes, a majority of five — and becomes the new term-2 leader, even though B was holding a longer log.

Is this a bug? No — and this is precisely why the commit rule matters. Entries 2 and 3 were never committed (they never reached a majority), so Raft never promised they would survive a leader change, and indeed C's new term simply proceeds without them; B will later be forced to discard its uncommitted tail and replace it with whatever C proposes. Compare this against the second snapshot, where entries 2 and 3 had reached a majority {A, B, C}. In that scenario, quorum intersection guarantees any future election-winning majority (also drawn from 5 nodes) must include at least one of A, B, or C — and that node's log, containing the committed entry, would block any candidate lacking it from winning a vote. Committed data is provably safe across leader changes; uncommitted data is provably not — and the boundary between the two is exactly the majority threshold computed above.

The misconception this chapter exists to correct

The mistake nearly every student makes on first contact with this topic is treating replication and consensus as the same thing: "if the data is copied to three machines, the system is safe." It is not. Plain primary-backup replication — where a primary pushes updates to backups and a monitoring script promotes a backup to primary whenever the old one seems unreachable — has no mechanism to stop two machines from both believing they are primary during a network partition. If the monitor on one side of a split network promotes backup B to primary while the original primary A is still alive and still accepting writes on the other side, you now have two primaries diverging in parallel — classic split-brain — and for a ledger system that means the same money can be spent twice, because two "authoritative" machines each independently confirmed it. Consensus protocols like Raft do not eliminate this risk by having more copies; they eliminate it with the term number and the majority-vote rule specifically: a stale leader cannot keep operating once any node has seen a higher term, and a new leader cannot win an election without collecting votes from a majority that quorum-intersects with every prior committing majority. The copies are necessary but not sufficient — the agreement protocol on top of the copies is what actually buys the safety.

Active recall

Attempt every question before reading its answer.

1. A cluster has 7 nodes. What is the majority quorum size, and how many simultaneous node failures can it tolerate?
2. A 5-node Raft leader in term 2 reports match_index = [5, 5, 5, 2, 2] and log_terms = [1, 1, 1, 2, 2] (terms of entries at index 1 through 5). What is the commit index?
3. Why can't a Raft leader commit an entry just because a majority replicated it, if that entry was written in an earlier term than the leader's current term?
4. Compare N = 5 and N = 6 in terms of quorum size and fault tolerance. Why do production systems rarely choose an even N?
5. A Dynamo-style system uses N = 5 replicas with read quorum R = 3 and write quorum W = 3. Show numerically why R + W > N guarantees that every read overlaps at least one replica from the most recent write, and name one cost this buys relative to Raft.
6. True or false: "A database with 3 replicas can survive any 2 simultaneous node failures without losing availability." Justify your answer with the majority formula.

Answers

1. Majority(7) = floor(7/2) + 1 = 3 + 1 = 4. Fault tolerance = floor((7-1)/2) = 3. The cluster needs at least 4 of 7 nodes reachable to make progress and can lose up to 3 nodes and keep operating.

2. Check index 5 first: count of entries ≥ 5 in [5,5,5,2,2] is 3 (the first three nodes), which meets majority(5) = 3, and log_terms[4] = 2 matches current_term = 2. So the commit index is 5 — everything up to and including index 5 is committed in a single step, since the highest index already satisfies both the majority and current-term conditions.

3. Because a later leader, elected in a still-higher term, can legally overwrite that entry through ordinary log replication before any current-term entry has been committed on top of it — the "majority replicated" snapshot at that earlier moment does not survive being observed retroactively. Raft avoids this entirely by never counting an earlier-term entry directly toward the commit decision; it only becomes safe once a current-term entry commits above it, dragging it along indirectly.

4. N = 5 gives majority 3, fault tolerance 2. N = 6 gives majority 4, fault tolerance floor(5/2) = 2 — identical fault tolerance to N = 5, but a strictly larger quorum needed for every write, meaning more machines must be reachable and more network round trips must complete before anything commits. The sixth node adds cost and latency risk without adding any safety margin, so odd N is preferred.

5. R + W = 3 + 3 = 6 > N = 5. Since any read quorum of 3 and any write quorum of 3 are both drawn from only 5 total replicas, 3 + 3 exceeds 5, so by the same pigeonhole argument used for Raft's quorum intersection, they cannot be disjoint — every read set must include at least one node that was part of the most recent write set, guaranteeing the read observes the latest value (or something newer). The cost, relative to Raft, is that this scheme typically has no single leader serializing writes, so concurrent writes to the same key from different clients can conflict and require a separate reconciliation step (e.g. version vectors or last-writer-wins) — it buys read/write flexibility at the price of a strong, single global ordering.

6. False. Majority(3) = 2. Losing 2 of 3 nodes leaves only 1 node standing, which cannot form a majority of 3 on its own — the system cannot accept new writes and loses availability, even though the single surviving node's already-committed data is not lost. The formula only guarantees tolerance of floor((3-1)/2) = 1 simultaneous failure, not 2.

Think About It

Think about this: How would you explain distributed systems: consensus & replication 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.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where distributed systems: consensus & replication is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting distributed systems: consensus & replication to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind distributed systems: consensus & replication, 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.