Demystifying Distributed Consensus: How Raft and Paxos Prevent Split-Brain

Demystifying Distributed Consensus: How Raft and Paxos Prevent Split-Brain

In single-node software, maintaining consistency is straightforward: memory locks, database ACID transactions, and sequential execution dictate the order of truth.

In cloud computing, servers fail, network switches drop packets, and cross-continental fiber lines experience transient partitions. If two partitioned halves of a cluster both believe they are the authoritative primary—a condition known as Split-Brain—they will accept contradictory writes, resulting in permanent data corruption.

How do systems like etcd (Kubernetes), CockroachDB, and Kafka achieve absolute agreement across unreliable networks? Through Consensus Protocols.

1. The Replicated State Machine (RSM) Model

Consensus protocols structure distributed systems as Replicated State Machines:

If identical deterministic state machines on multiple servers process an identical, identically-ordered sequence of log commands from an identical initial state, they will inevitably arrive at identical final states!

The entire purpose of consensus algorithms like Paxos and Raft is to ensure that all healthy servers agree on the exact contents and order of the replicated log.

2. Paxos vs. Raft: The Understandability Revolution

Leslie Lamport introduced Paxos in 1998. While mathematically elegant, multi-decree Paxos was notoriously difficult to implement in production without subtle divergence bugs.

In 2014, Ongaro and Ousterhout presented Raft, purposefully designed for understandability by decomposing consensus into three independent sub-problems:

1. Leader Election: A single leader is chosen; if it fails, a new one is elected.
2. Log Replication: The leader accepts commands from clients and replicates them to follower nodes.
3. Safety: If any server has applied an entry at index $i$, no other server will ever apply a different entry at index $i$.

3. Raft Leader Election and Quorum Mathematics

Every Raft node resides in one of three states:

• Follower: Passive; listens for heartbeats and vote requests.
• Candidate: Triggered when heartbeat timeout expires; requests votes to become leader.
• Leader: Handles all client writes and coordinates replication.

stateDiagram-v2
    [*] --> Follower: Node Boot / Join Cluster

    state Follower {
        ListenHeartbeat: Awaiting AppendEntries from Leader
        ResetElectionTimer: Reset Timer on Valid RPC
    }

    state Candidate {
        IncrementTerm: Increment Current Term
        VoteForSelf: Vote for Self
        SendRequestVote: Broadcast RequestVote RPCs to All Nodes
    }

    state Leader {
        Heartbeats: Broadcast Periodic AppendEntries Heartbeats
        ReplicateLog: Append and Replicate Client Commands
        CommitEntries: Commit Once Replicated on Quorum (> N/2)
    }

    Follower --> Candidate: Election Timeout Fires (Randomized 150-300ms)
    Candidate --> Leader: Quorum Votes Received (Majoritarian Consensus)
    Candidate --> Candidate: Split Vote Timeout / No Quorum
    Candidate --> Follower: Discovers Current Leader or Higher Term
    Leader --> Follower: Discovers Higher Term from Peer Node

Quorum and Split-Brain Prevention

In an $N$-node cluster, a valid decision requires a Quorum (Strict Majority):

• In a 3-node cluster, Quorum is 2. The cluster can tolerate 1 failure.
• In a 5-node cluster, Quorum is 3. The cluster can tolerate 2 failures.

Because any two majorities in a set must overlap in at least one node:

It is mathematically impossible for two independent leaders to be elected simultaneously during a network partition! The partitioned minority side simply fails to achieve quorum and refuses writes.

4. Log Matching Invariant

Raft enforces strict guarantees on log entries $(index, term)$:

• If two entries in different logs have the same index and term, they store the same command.
• If two entries in different logs have the same index and term, then their logs are identical in all preceding entries.

When a follower's log diverges from the leader's (due to uncommitted entries from an old partitioned term), the leader forces the follower's log to replicate its own by backing up nextIndex until a match is found, discarding uncommitted conflicting entries.

5. Randomized Election Timeouts

To avoid split-vote deadlocks where multiple candidates start elections at the exact same instant, Raft employs randomized election timeouts (e.g., uniformly picked between 150ms and 300ms).

This simple mechanism ensures that almost invariably, one candidate's timer expires first, allowing it to collect quorum votes and broadcast its heartbeat before competitors awaken.

Cloud Infrastructure at Kone Digital

In Kone Digital's Systems Architecture track, students implement Raft clusters from scratch in Go and Rust, gaining an unshakeable intuition for cloud reliability in our Cloud Infrastructure & DevOps Automation Track.