Distributed Systems # Consensus Algorithms Compared: Raft, Multi-Paxos, Viewstamped Replication, and EPaxos 2025-10-28Updated: 2026-11-1010 min read [Lucio Durán]() C.T.O. at LOi Also available in: [Español]() ## Why Consensus Is Hard (A Quick Refresher) The fundamental problem: N servers need to agree on a sequence of operations, even if up to F of them crash (where N \>= 2F + 1). This agreement must be: - **Safe**: All non-faulty servers agree on the same sequence - **Live**: The system eventually makes progress (assuming fewer than F+1 crashes and the network eventually delivers messages) The FLP impossibility result tells us we can't have both in an asynchronous network with even one crash failure. Every practical consensus algorithm works around this by using timeouts as failure detectors, which is technically violating the asynchronous model, but it works in practice because real networks have bounded-but-unknown delays. ## Raft: The Algorithm That Explains Itself Raft was designed for understandability, and it delivers on that promise. The algorithm decomposes into three subproblems: leader election, log replication, and safety. Let me focus on the pieces that are harder to implement than the paper suggests. ### Leader Election: The Subtle Parts The basic mechanism is simple: candidates increment their term, vote for themselves, and request votes from others. But the implementation details matter enormously. ```go type RaftNode struct { mu sync.Mutex state NodeState currentTerm uint64 votedFor *uint64 log []LogEntry // Election timing - these values matter more than you think electionTimeout time.Duration heartbeatTimeout time.Duration lastHeartbeat time.Time // Pre-vote protocol (Section 9.6 of Raft dissertation) preVoteEnabled bool } func (n *RaftNode) startElection() { n.mu.Lock() defer n.mu.Unlock() if n.preVoteEnabled { // Pre-vote: ask peers if they'd vote for us WITHOUT incrementing term // This prevents disruption from partitioned nodes n.runPreVote() return } n.currentTerm++ n.state = Candidate n.votedFor = &n.id n.persistState() // MUST be durable before sending RequestVote lastLogIndex, lastLogTerm := n.lastLogInfo() for _, peer := range n.peers { go func(p PeerID) { reply, err := n.sendRequestVote(p, &RequestVoteArgs{ Term: n.currentTerm, CandidateID: n.id, LastLogIndex: lastLogIndex, LastLogTerm: lastLogTerm, }) if err != nil { return } n.handleVoteResponse(reply) }(peer) } } ``` The pre-vote protocol is critical and often omitted from tutorials. Without it, a node that gets partitioned from the cluster keeps incrementing its term. When it rejoins, its artificially high term forces a new election, disrupting the healthy cluster. Pre-vote asks "would you vote for me?" without actually incrementing the term. If the answer is no (because the cluster already has a healthy leader), the node backs off. ### Log Compaction: Where The Pain Lives Snapshot installation and recovery need explicit handling beyond the log-compaction overview. The following code is an explanatory sketch. ```go type SnapshotManager struct { stateMachine StateMachine raftLog *RaftLog snapshotDir string // Concurrent snapshot support inProgress atomic.Bool lastIncluded struct { Index uint64 Term uint64 } } func (sm *SnapshotManager) TakeSnapshot() error { if !sm.inProgress.CompareAndSwap(false, true) { return ErrSnapshotInProgress } defer sm.inProgress.Store(false) // 1. Get a consistent point-in-time snapshot of the state machine // This MUST be atomic with respect to applied log entries snapshot, appliedIndex, appliedTerm := sm.stateMachine.Snapshot() // 2. Write to a temporary file first (crash safety) tmpPath := filepath.Join(sm.snapshotDir, fmt.Sprintf("snap-%d.tmp", appliedIndex)) finalPath := filepath.Join(sm.snapshotDir, fmt.Sprintf("snap-%d.dat", appliedIndex)) f, err := os.Create(tmpPath) if err != nil { return err } // 3. Write snapshot metadata + data header := SnapshotHeader{ LastIncludedIndex: appliedIndex, LastIncludedTerm: appliedTerm, Size: uint64(len(snapshot)), Checksum: crc32.ChecksumIEEE(snapshot), } if err := binary.Write(f, binary.LittleEndian, header); err != nil { f.Close() os.Remove(tmpPath) return err } if _, err := f.Write(snapshot); err != nil { f.Close() os.Remove(tmpPath) return err } // 4. Fsync before rename (critical for crash safety) if err := f.Sync(); err != nil { f.Close() os.Remove(tmpPath) return err } f.Close() // 5. Atomic rename if err := os.Rename(tmpPath, finalPath); err != nil { return err } // 6. Truncate the log up to the snapshot point sm.raftLog.TruncateBefore(appliedIndex) sm.lastIncluded.Index = appliedIndex sm.lastIncluded.Term = appliedTerm return nil } ``` The tricky parts: 1. **Taking the snapshot must not block log application.** If your state machine is a B-tree, you need either copy-on-write semantics or a snapshot isolation mechanism. BoltDB gives you this for free; a naive in-memory map doesn't. 2. **InstallSnapshot RPC is chunked.** When a follower is so far behind that the leader has already compacted its log, the leader sends its snapshot. For a multi-GB state machine, this must be chunked and resumable. The paper mentions this in one sentence. 3. **Crash recovery interleaves snapshots and logs.** On restart, you load the latest snapshot, then replay log entries after the snapshot's last included index. If you crashed between taking a snapshot and truncating the log, you might have overlapping entries. Your recovery logic needs to handle this. ## Multi-Paxos: A Protocol Without a Canonical Specification Here's the dirty secret about Multi-Paxos: there is no canonical Multi-Paxos paper. Lamport's original "The Part-Time Parliament" describes single-decree Paxos. The extension to multi-decree (a sequence of consensus instances) is described informally, and every implementation makes different choices. The core optimization of Multi-Paxos over basic Paxos: once a leader is established, it can skip the Prepare phase for subsequent log entries, going straight to Accept. This means steady-state operations only require one round-trip instead of two. ```go type MultiPaxosNode struct { proposerState struct { ballotNum BallotNumber isLeader bool maxSlot uint64 // Per-slot state for the accept phase accepts map[uint64]*AcceptState } acceptorState struct { promisedBallot BallotNumber // Per-slot: highest accepted ballot and value accepted map[uint64]AcceptedEntry } learnerState struct { chosen map[uint64]ChosenEntry } } func (n *MultiPaxosNode) Propose(value []byte) (uint64, error) { if !n.proposerState.isLeader { return 0, ErrNotLeader } slot := atomic.AddUint64(&n.proposerState.maxSlot, 1) // As established leader, skip Phase 1 (Prepare) // Go directly to Phase 2 (Accept) acceptMsg := &AcceptMessage{ Ballot: n.proposerState.ballotNum, Slot: slot, Value: value, } ackCount := 1 // Count self quorum := (len(n.peers) / 2) + 1 for _, peer := range n.peers { go func(p PeerID) { reply, err := n.sendAccept(p, acceptMsg) if err != nil { return } if reply.Ballot > n.proposerState.ballotNum { // Someone else has a higher ballot - we're no longer leader n.stepDown(reply.Ballot) return } if atomic.AddInt32(&ackCount, 1) >= int32(quorum) { n.markChosen(slot, value) } }(peer) } return slot, nil } ``` ### The Slot Gap Problem In Multi-Paxos, slots can be chosen out of order. Client A's request might get slot 5, and Client B's request might get slot 7, while slot 6 is still pending. When delivering commands to the state machine, you must deliver in order. This means you need a mechanism to fill gaps, either with no-ops or by re-proposing values for empty slots. This gap-filling logic is where most Multi-Paxos implementations have bugs. The interaction between gap-filling, leader changes, and the accept phase is subtle. If a new leader starts filling gaps concurrently with the old leader's accepts still in flight, you can end up with a slot being chosen with two different values unless the ballot number mechanism is correctly implemented. ## Viewstamped Replication: The Forgotten Middle Child VR predates Paxos in publication and is remarkably similar to Raft in structure, it has a primary (leader), views (terms), and a log. The key differences are in the view change protocol and the reconfiguration mechanism. ``` Normal Operation (simplified): 1. Client → Primary: REQUEST(op, client-id, request-num) 2. Primary: Assign op-number, append to log 3. Primary → Backups: PREPARE(view, op-number, op, commit-number) 4. Backups: Append to log, reply PREPARE-OK 5. Primary: After f+1 PREPARE-OKs, commit 6. Primary → Client: REPLY(view, request-num, result) ``` The interesting thing about VR is its view change protocol, which is more structured than Raft's election. When a backup suspects the primary has failed: 1. It sends ` START-VIEW-CHANGE ` messages 2. After receiving f such messages, a node sends ` DO-VIEW-CHANGE ` to the new primary (determined by round-robin) 3. The new primary collects f+1 ` DO-VIEW-CHANGE ` messages, selects the log with the latest data, and starts the new view The deterministic primary selection (round-robin based on view number) means there's no split-vote scenario, you don't need randomized timeouts like Raft. The tradeoff is less flexibility: you can't prefer a node with better hardware or lower latency to clients. ### Where VR Shines VR's reconfiguration protocol (changing the set of replicas) is significantly simpler than Raft's joint consensus approach. In VR, reconfiguration is just a special operation in the log. When it commits, the new configuration takes effect at that point in the log. Old replicas transfer state to new replicas, and the transition is clean. ## EPaxos: The Leaderless Promise EPaxos (Egalitarian Paxos) is the most intellectually ambitious of the four. Instead of funneling all operations through a leader, any replica can propose commands. Non-conflicting commands can be committed in a single round-trip (the fast path), and conflicting commands are resolved through a dependency graph. ### The Dependency Graph This is where EPaxos gets complicated. Every command carries a set of dependencies, other commands it must be executed after: ```go type EPaxosInstance struct { Command []byte Deps map[InstanceID]uint64 // dependency → sequence number SeqNum uint64 Status InstanceStatus // PreAccepted, Accepted, Committed, Executed Ballot BallotNumber } func (r *EPaxosReplica) StartCommand(cmd []byte) { inst := &EPaxosInstance{ Command: cmd, SeqNum: 0, Deps: make(map[InstanceID]uint64), Status: PreAccepted, } // Calculate initial dependencies and sequence number for id, other := range r.instances { if r.conflictsWithAny(cmd, other.Command) { inst.Deps[id] = other.SeqNum if other.SeqNum >= inst.SeqNum { inst.SeqNum = other.SeqNum + 1 } } } // Fast path: send PreAccept to a super-quorum superQuorum := (3*len(r.peers)/4) + 1 replies := r.broadcastPreAccept(inst) if r.fastPathSucceeded(replies, inst, superQuorum) { // All replicas agreed on the same dependencies inst.Status = Committed r.broadcastCommit(inst) } else { // Slow path: need explicit Accept phase r.mergedDeps(inst, replies) inst.Status = Accepted r.broadcastAccept(inst) // Then commit after majority ack } } ``` ### The Execution Problem Committing is easy. Executing is hard. Because commands are committed by different replicas with different dependency sets, you need a deterministic algorithm to linearize the dependency graph. This uses Tarjan's strongly connected components algorithm: 1. Build the dependency graph from committed instances 2. Find all strongly connected components (SCCs) 3. Execute SCCs in reverse topological order 4. Within each SCC, execute commands in sequence number order This means you can't execute a command the moment it's committed, you have to wait until all its dependencies are also committed, and then compute the execution order. In practice, this adds latency variance that the fast-path savings don't always compensate for. ## Comparing implementations Protocol names alone do not determine performance. Compare concrete implementations under the same durability settings, workload, conflict rate, batching policy and network conditions. Publish the harness, versions and repeated results before drawing numerical conclusions. No reproducible benchmark is supplied here. ## What I'd Choose Today For most systems: **Raft with etcd's optimizations** (pipelining, learner nodes, pre-vote, leader lease for reads). The ecosystem is unmatched, [etcd](), [CockroachDB](), [TiKV](), and [Consul]() all use Raft variants, and their battle-tested implementations are available as libraries. For geo-distributed systems with mostly non-conflicting operations: **EPaxos**, but only if you have the engineering resources to handle the implementation complexity and the debugging nightmare that is dependency graph resolution. For learning and building intuition: implement **Raft first, then VR**. The similarities will crystallize your understanding, and the differences in view change vs. election will teach you why these design choices matter. Multi-Paxos is the right answer if you need maximum throughput on a single leader and you're willing to invest in a custom implementation. But honestly, at that point, you should probably just use etcd or CockroachDB and focus your engineering effort on your actual product. ## Editorial method and scope Reviewed on November 10, 2026. Unsupported claims of personal production experience and numerical results were removed. The remaining examples explain techniques; their presence is not a claim that they were executed in this review. This revision is not a complete validation of every API, version or code sample in the article. ## Frequently asked questions ### Which consensus algorithm should I use for a new project? Raft, unless you have a specific reason not to. It's the most well-understood, has the most production implementations, the best debugging tooling, and the clearest specification. Multi-Paxos can be more efficient for high-throughput workloads, but the implementation complexity is significantly higher. ### Is EPaxos actually better than Raft in practice? It depends on your workload. EPaxos eliminates the leader bottleneck and achieves lower latency for non-conflicting commands in geo-distributed deployments. But the implementation complexity is an order of magnitude higher, the recovery protocol is notoriously difficult to get right, and conflicting commands can cause significant performance degradation. ### What's the difference between Paxos and Multi-Paxos? Classic Paxos is a protocol for agreeing on a single value. Multi-Paxos extends it to a sequence of values (a replicated log) by electing a stable leader that can skip the prepare phase for subsequent log entries, amortizing the cost of leader election across many operations. ## Tips 1. **LuchoTip:** Raft's leader lease optimization (where the leader serves reads without quorum) breaks linearizability if clock skew exceeds the lease duration. Always use ` ReadIndex ` or ` ReadOnlySafe ` for reads that must be linearizable. 2. **LuchoTip:** When implementing log compaction in Raft, snapshot the state machine on a separate goroutine/thread and use a copy-on-write data structure. Blocking the main loop during snapshotting causes election timeouts in large clusters. 3. **LuchoTip:** EPaxos's fast-path requires a super-quorum (⌊3F/4⌋+1 for F failures). In a 5-node cluster, that's 4 out of 5 nodes. One slow node kills your fast path, which is why EPaxos performs worse than Raft in heterogeneous networks despite looking better on paper. 4. **LuchoTip:** For Multi-Paxos, the distinction between ` prepare ` and ` accept ` phases is where most bugs hide. If your leader crashes between sending accepts and receiving a quorum of acks, the new leader's prepare phase MUST discover those in-flight accepts. Use a persistent log, not an in-memory map. - raft - paxos - epaxos - consensus - distributed-systems - viewstamped-replication - leader-election - log-replication [Back to Blog]()