The Paxos Protocol

Paxos operates with three roles:

1. Proposers: Propose values for consensus
2. Acceptors: Vote on proposed values
3. Learners: Learn the chosen value

The protocol proceeds in two phases:

// Paxos Phase 1: Prepare
type Proposer struct {
    proposalNumber int
    acceptors      []Acceptor
}

func (p *Proposer) Prepare() PrepareResponse {
    p.proposalNumber++
    
    // Send prepare(n) to majority of acceptors
    responses := make(chan PrepareResponse, len(p.acceptors))
    
    for _, acceptor := range p.acceptors {
        go func(a Acceptor) {
            responses <- a.ReceivePrepare(p.proposalNumber)
        }(acceptor)
    }
    
    // Wait for majority
    majority := len(p.acceptors)/2 + 1
    promises := []PrepareResponse{}
    
    for i := 0; i < majority; i++ {
        promises = append(promises, <-responses)
    }
    
    return p.findHighestAccepted(promises)
}

type Acceptor struct {
    promisedNumber  int
    acceptedNumber  int
    acceptedValue   interface{}
}

func (a *Acceptor) ReceivePrepare(n int) PrepareResponse {
    if n > a.promisedNumber {
        a.promisedNumber = n
        return PrepareResponse{
            Promise:        true,
            AcceptedNumber: a.acceptedNumber,
            AcceptedValue:  a.acceptedValue,
        }
    }
    return PrepareResponse{Promise: false}
}

// Paxos Phase 2: Accept
func (p *Proposer) Accept(value interface{}) bool {
    // Send accept(n, value) to majority of acceptors
    responses := make(chan bool, len(p.acceptors))
    
    for _, acceptor := range p.acceptors {
        go func(a Acceptor) {
            responses <- a.ReceiveAccept(p.proposalNumber, value)
        }(acceptor)
    }
    
    // Wait for majority
    majority := len(p.acceptors)/2 + 1
    accepted := 0
    
    for i := 0; i < majority; i++ {
        if <-responses {
            accepted++
        }
    }
    
    return accepted >= majority
}

func (a *Acceptor) ReceiveAccept(n int, value interface{}) bool {
    if n >= a.promisedNumber {
        a.promisedNumber = n
        a.acceptedNumber = n
        a.acceptedValue = value
        return true
    }
    return false
}

The Complexity of Paxos

Paxos provides strong safety guarantees:

• Validity: Only proposed values can be chosen
• Agreement: At most one value is chosen
• Termination: Eventually, a value is chosen (under reasonable assumptions)

However, Paxos is notoriously difficult to implement correctly. The protocol handles multiple proposers competing simultaneously, message reordering, and partial failures. This complexity led to many incorrect implementations and the search for alternatives.

Leader Election

Raft nodes exist in three states: follower, candidate, or leader.

enum NodeState {
  Follower,
  Candidate,
  Leader
}

class RaftNode {
  private state: NodeState = NodeState.Follower;
  private currentTerm: number = 0;
  private votedFor: string | null = null;
  private log: LogEntry[] = [];
  private commitIndex: number = 0;
  private lastApplied: number = 0;
  
  // Election timeout triggers leader election
  private electionTimeout: number = randomRange(150, 300);
  
  startElection(): void {
    // Transition to candidate
    this.state = NodeState.Candidate;
    this.currentTerm++;
    this.votedFor = this.nodeId;
    
    let votesReceived = 1; // Vote for self
    
    // Request votes from all peers
    for (const peer of this.peers) {
      const response = peer.requestVote({
        term: this.currentTerm,
        candidateId: this.nodeId,
        lastLogIndex: this.log.length - 1,
        lastLogTerm: this.log[this.log.length - 1]?.term || 0
      });
      
      if (response.voteGranted) {
        votesReceived++;
      }
      
      // Check if we have majority
      if (votesReceived > this.peers.length / 2) {
        this.becomeLeader();
        return;
      }
    }
    
    // Election failed, restart timeout
    this.resetElectionTimeout();
  }
  
  requestVote(request: VoteRequest): VoteResponse {
    // Reply false if term < currentTerm
    if (request.term < this.currentTerm) {
      return { term: this.currentTerm, voteGranted: false };
    }
    
    // If votedFor is null or candidateId, and candidate's log is
    // at least as up-to-date as receiver's log, grant vote
    if ((this.votedFor === null || this.votedFor === request.candidateId) &&
        this.isLogUpToDate(request.lastLogIndex, request.lastLogTerm)) {
      this.votedFor = request.candidateId;
      this.resetElectionTimeout();
      return { term: this.currentTerm, voteGranted: true };
    }
    
    return { term: this.currentTerm, voteGranted: false };
  }
}

Log Replication

Once elected, the leader handles all client requests and replicates its log to followers.

class RaftNode {
  // Leader state
  private nextIndex: Map<string, number> = new Map();
  private matchIndex: Map<string, number> = new Map();
  
  appendEntries(request: AppendEntriesRequest): AppendEntriesResponse {
    // Reply false if term < currentTerm
    if (request.term < this.currentTerm) {
      return { term: this.currentTerm, success: false };
    }
    
    // Reset election timeout - we heard from leader
    this.resetElectionTimeout();
    
    // Reply false if log doesn't contain an entry at prevLogIndex
    // whose term matches prevLogTerm
    if (request.prevLogIndex >= 0) {
      const entry = this.log[request.prevLogIndex];
      if (!entry || entry.term !== request.prevLogTerm) {
        return { term: this.currentTerm, success: false };
      }
    }
    
    // If an existing entry conflicts with a new one,
    // delete the existing entry and all that follow it
    for (let i = 0; i < request.entries.length; i++) {
      const index = request.prevLogIndex + 1 + i;
      const newEntry = request.entries[i];
      
      if (this.log[index] && this.log[index].term !== newEntry.term) {
        this.log = this.log.slice(0, index);
      }
      
      if (index >= this.log.length) {
        this.log.push(newEntry);
      }
    }
    
    // Update commit index
    if (request.leaderCommit > this.commitIndex) {
      this.commitIndex = Math.min(
        request.leaderCommit,
        this.log.length - 1
      );
    }
    
    return { term: this.currentTerm, success: true };
  }
  
  replicateLog(): void {
    if (this.state !== NodeState.Leader) return;
    
    for (const peer of this.peers) {
      const nextIdx = this.nextIndex.get(peer.id) || 0;
      const prevLogIndex = nextIdx - 1;
      const prevLogTerm = prevLogIndex >= 0 
        ? this.log[prevLogIndex].term 
        : 0;
      
      const response = peer.appendEntries({
        term: this.currentTerm,
        leaderId: this.nodeId,
        prevLogIndex,
        prevLogTerm,
        entries: this.log.slice(nextIdx),
        leaderCommit: this.commitIndex
      });
      
      if (response.success) {
        this.nextIndex.set(peer.id, this.log.length);
        this.matchIndex.set(peer.id, this.log.length - 1);
        this.updateCommitIndex();
      } else if (response.term > this.currentTerm) {
        // Discovered higher term, step down
        this.becomeFollower(response.term);
      } else {
        // Decrement nextIndex and retry
        this.nextIndex.set(peer.id, nextIdx - 1);
      }
    }
  }
}

Safety Properties

Raft's safety guarantees ensure that:

1. Election Safety: At most one leader per term
2. Leader Append-Only: Leaders never overwrite or delete entries
3. Log Matching: If two logs contain an entry with the same index and term, all preceding entries are identical
4. Leader Completeness: If a log entry is committed in a given term, it will be present in the leaders' logs for all higher terms
5. State Machine Safety: If a server has applied a log entry at a given index, no other server will apply a different entry for that index

etcd: Raft for Kubernetes

etcd, the distributed key-value store backing Kubernetes, uses Raft for consensus.

// Simplified etcd Raft usage
import "go.etcd.io/etcd/raft/v3"

type EtcdNode struct {
    raftNode  raft.Node
    storage   *raft.MemoryStorage
    proposeC  chan string
    commitC   chan *commit
}

func (n *EtcdNode) processCommits() {
    for commit := range n.commitC {
        if commit.data != nil {
            // Apply committed entry to state machine
            n.applyToStateMachine(commit.data)
        }
    }
}

func (n *EtcdNode) propose(data []byte) {
    // Propose to Raft
    n.raftNode.Propose(context.TODO(), data)
}

CockroachDB: Multi-Raft

CockroachDB uses a "multi-Raft" approach, running one Raft group per range of keys.

-- In CockroachDB, consensus happens per range
-- Each range has its own Raft group
SHOW RANGES FROM TABLE users;

-- Output shows multiple ranges, each with Raft replicas:
-- range_id | start_key | end_key | replicas
-- 1        | /Min      | /Table/50 | {1,2,3}
-- 2        | /Table/50 | /Table/51 | {2,3,4}

Flexible Paxos

Recent research shows that Paxos doesn't require majorities in both phases—only the intersection must form a majority. This "Flexible Paxos" can improve availability.

class FlexiblePaxos:
    def __init__(self, n_acceptors):
        self.n_acceptors = n_acceptors
        # Phase 1 quorum: 2 nodes
        # Phase 2 quorum: 3 nodes
        # Intersection: at least 1 node
        # 2 + 3 > 4, so guaranteed intersection
        self.phase1_quorum = 2
        self.phase2_quorum = 3
        
    def can_commit(self, phase1_responses, phase2_responses):
        return (len(phase1_responses) >= self.phase1_quorum and
                len(phase2_responses) >= self.phase2_quorum)

EPaxos: Leaderless Consensus

Egalitarian Paxos (EPaxos) eliminates the leader bottleneck by allowing any replica to act as leader for its commands.

Viewstamped Replication

VR, developed in the 1980s (before Paxos was published), uses a similar approach to Raft but was less well known.

When to Use Consensus

Consensus is necessary when:

• Strong consistency is required (financial transactions, distributed locks)
• Coordination is needed (leader election, configuration management)
• Ordering matters (event sequencing, log replication)

Consensus is overkill when:

• Eventual consistency suffices (DNS, caches, analytics)
• Commutativity allows for conflict-free replication (CRDTs)
• Single writer pattern can be used

Performance Implications

# Consensus latency components
import time

class ConsensusLatency:
    def estimate_latency(self):
        # Network RTT to majority of nodes
        network_rtt = 50  # ms, depends on geography
        
        # Disk write latency (fsync for durability)
        disk_write = 10  # ms, depends on storage
        
        # Processing time
        processing = 1  # ms
        
        # Minimum latency for one round
        return network_rtt + disk_write + processing
        
# For cross-datacenter deployment:
# 3 datacenters, 5 nodes total
# RTT between DCs: 100ms
# Total latency: ~110ms per consensus round

# For single datacenter:
# RTT: 1ms
# Total latency: ~12ms per consensus round