Consensus Systems

Log replication

Prerequisites

graph TD
  Dist[Distributed systems overview] --> CS[Consensus Systems]
  Prob[Probability basics] --> CS
  RaftVG[Raft vs Gossip] --> CS
  CAP[CAP / quorum intuition] --> CS

When to use

• Replicated state machines where every node must apply the same ordered log (etcd, Consul, ZooKeeper/ZAB).
• Crash-fault-tolerant (CFT) clusters with honest nodes — Paxos, Raft, or ZAB with majority quorums.
• Configuration and coordination (leader election, distributed locks) rather than high-throughput AP data planes.

When not to use

• Byzantine (malicious) peers on open networks — need BFT ((N \ge 3f+1)) or probabilistic chains, not plain Raft alone.
• Massive write fan-out across hundreds of nodes — quorum replication is (O(N)) per write; consider gossip or sharded logs.
• Eventually consistent caches where stale reads are acceptable — CRDTs or gossip may be simpler than a full consensus log.

Lab

On the interactive consensus systems lab, step Raft log replication: leader append → AppendEntries → quorum commit. Try ZooKeeper (N=5), Partition inject (majority commits, minority stale), or No quorum on A (split leaves too few nodes on the leader side). Predict whether an entry commits within the suggested steps, then reveal quorum intersection (Q+Q>N) vs ACK counts.

Simple Fundamental Explanation

Imagine 5 generals surrounding a city. They can only communicate via messengers on horseback. They must all attack at dawn, or all retreat. If only 2 attack, they will be slaughtered.

A messenger rides to General B and says “Attack.” General B must know:

1. Did the Commander actually send this, or is the messenger a traitor lying to me?
2. Did Generals C, D, and E also receive the “Attack” message?
3. If they did receive it, will they actually obey it, or are they traitors?

This is the Byzantine Generals Problem. In distributed computing, a Consensus System is the mathematical algorithm used to force a cluster of independent, unreliable computers to definitively agree on a single shared state, even if the network is dropping messages, or some of the computers are actively malfunctioning (or maliciously lying).

---

Deep Dive: How It Works Under the Hood

The holy grail of distributed systems is reaching consensus on a sequence of values (the Replicated State Machine). If all nodes agree on the exact order of a log of commands, they will all process the commands in the same order and arrive at the exact same state.

Crash-Fault Tolerance (CFT)

Most internal data center algorithms (like Paxos or Raft) only deal with Crash-Fault Tolerance. They assume nodes might die or network cables might be cut, but they assume nodes never lie. If Node A sends a message saying “Value is 5”, the message is trusted.

These algorithms rely on the concept of Quorum. You do not need all $N$ nodes to agree. You only need a strict majority ($>N/2$). If you have 5 nodes, you need 3 to agree. Because any two majorities of the same group must overlap by at least one node, the mathematical property of intersection guarantees that the system can never accidentally agree on two different things simultaneously (Split-Brain).

Byzantine Fault Tolerance (BFT)

In open networks (like Blockchains), nodes will lie. An attacker will run a node that tells half the network “Attack” and the other half “Retreat”. To survive BFT, a simple majority is not enough. The algorithm must mathematically isolate the traitors. BFT algorithms (like PBFT) require intense, multi-round cryptographic voting and require a supermajority of honest nodes.

Visual Diagram: Raft Quorum

Cluster of 5 Nodes (A, B, C, D, E)

Node A (Leader) wants to commit "X=10".
A writes "X=10" to local log.
A sends message to B, C, D, E.

B receives -> Replies OK.
C receives -> Replies OK.
D receives -> Network Drops Packet! (Timeout)
E receives -> Hard Drive Crashes! (Offline)

A counts ACKs: Itself(1) + B(1) + C(1) = 3 ACKs.
3 is a majority of 5. Quorum achieved!
A commits the data and tells the client "Success."

Even though D and E are broken, the system survives and proceeds safely.

---

Practical Example: ZooKeeper and Configuration Management

Apache ZooKeeper and HashiCorp Consul are foundational consensus systems used by massive internet companies.

Imagine a microservice architecture where 1,000 web servers need to know the IP address of the primary Master Database. If the Master Database crashes, a failover script promotes a Replica to be the new Master.

If the failover script just broadcast the new IP to the 1,000 servers, network lag might mean 500 servers get the message, and 500 don’t. Half the traffic goes to the new database, half goes to the broken one. Data corruption ensues.

Instead, the cluster’s configuration is stored inside a 5-node ZooKeeper cluster running a consensus algorithm (ZAB). When the failover happens, the script asks ZooKeeper to update the IP. ZooKeeper runs the consensus math. Only when 3 out of 5 ZooKeeper nodes mathematically lock in the new IP does the cluster officially accept the change. The 1,000 web servers constantly poll ZooKeeper for the “One True State” of the cluster.

---

The Mathematics: Equations and In-Depth Analysis

1. The Quorum Intersection Property

Let $V$ be the set of all nodes in the system, where $|V|=N$. A quorum system is a collection of subsets of $V$, called quorums, such that every two quorums intersect. If we define a quorum as any set containing $Q$ nodes, the intersection property requires:

$$Q+Q>N⟹Q>\frac{N}{2}$$

This simple inequality is the bedrock of safety in Paxos and Raft. Because any two quorums must overlap by at least one node, and nodes can only vote for one value per term, it is mathematically impossible for the system to achieve a quorum for Value A and a separate quorum for Value B in the same term.

2. Fault Tolerance Bounds

How many failures $f$ can the system tolerate? Because $Q=f+1$ (you need the failures plus one honest node to make a majority), and $N=Q+f$ (the quorum plus the remaining failed nodes), we substitute:

$$N=(f+1)+f=2f+1$$

Therefore, to tolerate $f$ crash-fault failures, you need exactly $2f+1$ nodes.

• Tolerate 1 failure $\to$ Need 3 nodes.
• Tolerate 2 failures $\to$ Need 5 nodes.

3. The Byzantine Bound

In a Byzantine environment, the traitor nodes can actively vote maliciously. To reach consensus, the honest nodes must outnumber the traitors not just by a simple majority, but they must be able to form a strict majority even if all traitors vote against them, and they must do this even if $f$ honest nodes happen to be offline due to normal network delays.

The math shifts drastically. The intersection of two honest quorums must be large enough to drown out the traitors. The mathematical proof shows that a deterministic BFT system requires:

$$N\ge 3f+1$$

To tolerate $f=1$ traitor, you need 4 nodes. To tolerate $f=33$ traitors, you need 100 nodes. The required supermajority makes BFT incredibly slow compared to CFT.

Lab

Step through simplified Raft log replication: the leader appends an entry, fans out AppendEntries, and commits after quorum Q = ⌊N/2⌋ + 1. Inject a network partition to see majority commit vs minority stall.

Replicas (N)5 nodes (N=5)

Replication stepstep 0

Network partition

ZooKeeper (N=5)Partition injectNo quorum on A

PlayAppend & replicateReset log

Full mesh — all 5 nodes reachable.

Gold cells = committed log index; amber = pending; dashed nodes = partitioned / stale. BFT needs f≤1 (N≥4=3f+1) for one traitor.

0

1

2

3

4

N0

N1

N2

N3

N4

With N = 5, quorum Q = 3, will the leader commit a log entry within 2 replication steps? (Step 0, committed index 0.)

Yes — committed within steps thresholdNo — takes longer or never commits (no quorum)

Step 0: Empty replicated log — leader elected at node 0. Awaiting more follower ACKs.