Distributed Consensus Internals: Raft vs. Multi-Paxos in High-Availability Cloud Engines

In a single-server architecture, transactional consistency is trivial: a single CPU acquires a mutex, appends a mutation to an on-disk write-ahead log, and commits the transaction. However, when an application scales across a distributed cluster of nodes—where network packets can be arbitrarily delayed, reordered, dropped, or machines can crash without warning—achieving atomic agreement becomes the single hardest challenge in computer science.

This fundamental problem is solved by Distributed Consensus: the mathematical protocol that guarantees a collection of independent nodes agree on a deterministic sequence of state transitions, even when a minority of nodes experience catastrophic hardware or network failures.

Distributed consensus powers the mission-critical foundation of modern cloud infrastructure: Kubernetes (etcd), Distributed SQL (CockroachDB, TiDB/TiKV, Google Spanner), Service Discovery (HashiCorp Consul), and Distributed Storage (Ceph, Apache Kafka KRaft).

In this systems engineering guide, we dissect the internal mechanics of the two defining consensus algorithms—Raft and Multi-Paxos. We will explore the FLP Impossibility theorem, analyze leader election terms, log matching safety invariants, and joint consensus cluster reconfigurations, and build a working Replicated State Machine in Go.

The Theoretical Barrier: The FLP Impossibility Theorem

In 1985, Fischer, Lynch, and Paterson published one of the most famous impossibility results in computer science (the FLP Theorem):

To overcome FLP, practical consensus protocols (Paxos, Raft) make a partially synchronous assumption: they guarantee 100% Safety under all network conditions (even infinite partitions or message reordering), but rely on randomized timeouts or leader leases to ensure Liveness whenever the network is reasonably stable.

The Foundation: Replicated State Machines (RSM)

Consensus protocols do not just agree on a single arbitrary value; they implement a Replicated State Machine (RSM):

Replicated State Machine Architecture:

Client Request: "SET balance:user_42 = $500"
       │
       ▼
┌────────────────────────────────────────────────────────┐
│ Leader Node                                            │
│                                                        │
│  [ Consensus Module (Raft / Multi-Paxos) ]             │
│           │                                            │
│           ▼ (Appends entry)                            │
│  [ Replicated Write-Ahead Log (WAL) ]                  │
│     Index 1: SET a=1 (Committed)                       │
│     Index 2: SET b=2 (Committed)                       │
│     Index 3: SET balance:user_42=$500 (Pending Quorum) │
│           │                                            │
│           ▼ (Replicate across network to Followers)    │
└───────────┼────────────────────────────────────────────┘
            │
      RPC: AppendEntries / Accept
            │
            ├───> Follower 1 (Logs entry & ACK)
            ├───> Follower 2 (Logs entry & ACK)
            │
            ▼ (Quorum Majority Achieved: 3 of 5 Nodes)
┌────────────────────────────────────────────────────────┐
│ State Machine (Deterministic Key-Value / SQL Engine)   │
│   Applies entry in strict index order -> Updates RAM   │
│   Returns success to Client                            │
└────────────────────────────────────────────────────────┘

The Deterministic State Machine Property: If two identical state machines start in the same initial state $S_0$ and apply the exact same sequence of deterministic state transitions $\mathcal{T} = [t_1, t_2, \dots, t_n]$, they are mathematically guaranteed to end up in the exact same state $S_n$.

Raft: Consensus Designed for Understandability & Safety

Introduced in 2014 by Ongaro and Ousterhout at Stanford, Raft decomposes the consensus problem into three independent, cleanly separated sub-problems:

1. Leader Election: Exactly one leader is elected when an existing leader fails.
2. Log Replication: The leader accepts commands from clients and replicates them across followers, forcing followers' logs to match its own.
3. Safety Invariants: If any server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for that index.

1. Server Roles and Term Lifecycles

In Raft, every node exists in one of three states: Leader, Follower, or Candidate. Time is divided into arbitrary numbered Terms (monotonically increasing logical clocks acting as logical epochs):

Raft State Transitions:

                   ┌─────────────┐
                   │  Follower   │ <───────────┐
                   └──────┬──────┘             │
     Election timeout     │                    │
     elapses, starts vote │                    │ Discovers current Leader
                          ▼                    │ or higher Term
                   ┌─────────────┐             │
                   │  Candidate  │ ────────────┘
                   └──────┬──────┘
       Receives majority  │
       of votes in Term   ▼
                   ┌─────────────┐
                   │   Leader    │
                   └─────────────┘

2. Randomized Election Timeouts: Split-Vote Avoidance

To prevent the "Split-Vote" pathology (where multiple candidates initiate an election simultaneously, split the vote evenly, and cause repeated election deadlocks), Raft uses Randomized Election Timeouts (e.g., chosen uniformly between $150\text{ms}$ and $300\text{ms}$).

The first node whose timer expires increments its term, votes for itself, and broadcasts RequestVote RPCs. It collects a majority quorum ($\lfloor N/2 \rfloor + 1$) before other candidates' timers trigger, winning the term decisively.

3. The 5 Core Raft Safety Invariants

Multi-Paxos: The Classic Two-Phase Consensus Engine

Proposed by Leslie Lamport in 1989, Paxos is the foundational consensus protocol. While Basic Paxos agrees on a single value, Multi-Paxos pipelines consensus rounds to replicate an unbounded sequence of log entries.

Multi-Paxos Phase 1 vs Phase 2 Optimization:

Phase 1 (Leader Election / Instance Setup - Executed ONCE per Leader Epoch):
Proposer                    Acceptors (Quorum)
   │                               │
   ├────── Prepare(Proposal N) ───>│  (Promise: will not accept proposals < N)
   │<───── Promise(N, max_val) ────┤
   │                               │
[ Leader Lease Established! Subsequent writes skip Phase 1 entirely ]

Phase 2 (Steady-State Log Replication - 1 Round Trip per Log Entry):
Proposer                    Acceptors (Quorum)
   │                               │
   ├────── Accept(Index i, N, V) ─>│  (Acceptors persist to disk)
   │<───── Accepted(Index i, N) ───┤  (Majority ACK -> Entry is COMMITTED!)
   │                               │

Multi-Paxos Optimizations:

• Phase 1 Amortization: By bundling the Prepare round across all log instances into a single leader lease, steady-state writes execute in a single round-trip (Phase 2 Accept $\to$ Accepted).
• Out-of-Order Commit Pipelining: Unlike Raft (which enforces strict contiguous log prefix matching), Multi-Paxos permits instances to commit out of order, filling in log gaps asynchronously.

Detailed Comparison: Raft vs. Multi-Paxos

Cluster Membership Reconfiguration: Joint Consensus

In production clusters, servers eventually fail permanently, disks run out of capacity, or hardware needs migration. Changing cluster configuration from 3 nodes to 5 nodes cannot happen instantaneously across all machines.

If nodes switch independently, a split-brain condition can occur where two disjoint majorities elect two separate leaders:

The Split-Brain Risk in Direct Reconfiguration:

Old Cluster (3 Nodes): { Node 1, Node 2, Node 3 } -> Majority Quorum = 2
New Cluster (5 Nodes): { Node 1, Node 2, Node 3, Node 4, Node 5 } -> Majority Quorum = 3

If Node 1 and Node 2 switch first, they form a majority for the Old Cluster.
Meanwhile, Node 3, 4, 5 switch to the New Cluster and form a separate majority of 3.
RESULT: Two concurrent leaders in the same epoch -> CATASTROPHIC DATA CORRUPTION!

Raft's Solution: Joint Consensus

Raft solves this by transitioning through an intermediate two-phase configuration called Joint Consensus ($C_{\text{old,new}}$):

• Log entries and configuration changes must be committed by separate majority quorums from BOTH $C_{\text{old}}$ AND $C_{\text{new}}$ simultaneously.
• Once $C_{\text{old,new}}$ is committed, the leader broadcasts the final $C_{\text{new}}$ configuration. This mathematically prevents any two disjoint majorities from ever coexisting.

Hands-On: Building a Replicated State Machine in Go

Below is a working implementation of a concurrent, thread-safe Replicated State Machine engine in Go featuring Term tracking, Write-Ahead Logging, and Quorum commit verification:

package main

import (
	"fmt"
	"sync"
	"time"
)

type LogEntry struct {
	Index uint64
	Term  uint64
	Key   string
	Value string
}

type RaftNode struct {
	mu          sync.Mutex
	id          int
	peers       []*RaftNode
	currentTerm uint64
	votedFor    int
	log         []LogEntry
	commitIndex uint64
	lastApplied uint64
	state       string // "Leader", "Follower", "Candidate"
	kvStore     map[string]string
}

func NewRaftNode(id int) *RaftNode {
	return &RaftNode{
		id:          id,
		currentTerm: 0,
		votedFor:    -1,
		log:         make([]LogEntry, 0),
		commitIndex: 0,
		lastApplied: 0,
		state:       "Follower",
		kvStore:     make(map[string]string),
	}
}

// Propose proposes a new key-value mutation to the Leader
func (rn *RaftNode) Propose(key, value string) bool {
	rn.mu.Lock()
	if rn.state != "Leader" {
		rn.mu.Unlock()
		return false // Reject writes if not current term leader
	}

	newIndex := uint64(len(rn.log) + 1)
	entry := LogEntry{
		Index: newIndex,
		Term:  rn.currentTerm,
		Key:   key,
		Value: value,
	}
	rn.log = append(rn.log, entry)
	rn.mu.Unlock()

	// Broadcast AppendEntries to peers to achieve majority quorum
	ackCount := 1
	var ackMu sync.Mutex
	var wg sync.WaitGroup

	for _, peer := range rn.peers {
		if peer.id == rn.id {
			continue
		}
		wg.Add(1)
		go func(p *RaftNode) {
			defer wg.Done()
			if p.AppendEntry(rn.currentTerm, entry) {
				ackMu.Lock()
				ackCount++
				ackMu.Unlock()
			}
		}(peer)
	}

	wg.Wait()

	// Check if majority quorum achieved: (len(peers)/2) + 1
	rn.mu.Lock()
	defer rn.mu.Unlock()
	majority := (len(rn.peers) / 2) + 1
	if ackCount >= majority {
		rn.commitIndex = newIndex
		rn.applyToStateMachine()
		fmt.Printf("[Leader Node %d] Committed Index %d: Key '%s' = '%s' (Quorum: %d/%d)\n",
			rn.id, newIndex, key, value, ackCount, len(rn.peers))
		return true
	}

	return false
}

// AppendEntry handles incoming replication RPCs from the leader
func (rn *RaftNode) AppendEntry(term uint64, entry LogEntry) bool {
	rn.mu.Lock()
	defer rn.mu.Unlock()

	// Safety check: Reject entries from stale terms
	if term < rn.currentTerm {
		return false
	}

	rn.log = append(rn.log, entry)
	rn.commitIndex = entry.Index
	rn.applyToStateMachine()
	return true
}

func (rn *RaftNode) applyToStateMachine() {
	for rn.lastApplied < rn.commitIndex {
		rn.lastApplied++
		entry := rn.log[rn.lastApplied-1]
		rn.kvStore[entry.Key] = entry.Value
	}
}

func main() {
	// Initialize a 5-node distributed cluster
	cluster := make([]*RaftNode, 5)
	for i := 0; i < 5; i++ {
		cluster[i] = NewRaftNode(i)
	}
	for i := 0; i < 5; i++ {
		cluster[i].peers = cluster
	}

	// Elect Node 0 as Leader for Term 1
	cluster[0].mu.Lock()
	cluster[0].state = "Leader"
	cluster[0].currentTerm = 1
	cluster[0].mu.Unlock()

	fmt.Println("=== Starting Distributed State Machine Transactions ===")
	cluster[0].Propose("user:100", "Alice")
	cluster[0].Propose("user:101", "Bob")
	cluster[0].Propose("user:102", "Charlie")

	time.Sleep(100 * time.Millisecond)

	// Verify all cluster state machines have identical values!
	fmt.Println("\n=== Verifying Cluster State Machine Consistency ===")
	for _, node := range cluster {
		node.mu.Lock()
		fmt.Printf("Node %d KV Store: user:100='%s', user:101='%s', user:102='%s'\n",
			node.id, node.kvStore["user:100"], node.kvStore["user:101"], node.kvStore["user:102"])
		node.mu.Unlock()
	}
}

Summary & Architecture Roadmap

• Consensus is About Quorum Intersection: Any two majorities of size $\lfloor N/2 \rfloor + 1$ are mathematically guaranteed to share at least one overlapping node. That single overlapping node guarantees that committed entries are never lost.
• Raft for Engineering Velocity: Raft enforces strict leader-driven contiguous logs, making system state machines vastly easier to implement, debug, formally verify, and maintain.
• Multi-Paxos for High-Latency Wide-Area Pipelines: Multi-Paxos excels in geo-distributed systems (like Google Spanner) where out-of-order execution and multi-proposer flexibility reduce wide-area network latency hops.
• Always Implement Log Compaction: In long-running production systems, write-ahead logs cannot grow infinitely. Implement periodic snapshotting to truncate committed WAL entries and bound recovery times.