distributed-systems-consensus-paxos

Paxos consensus algorithm including Basic Paxos, Multi-Paxos, roles, phases, and practical implementations

Paxos Consensus

Scope: Paxos algorithm, Basic Paxos, Multi-Paxos, roles, phases, practical implementations Lines: ~330 Last Updated: 2025-10-27 Format Version: 1.0 (Atomic)

---

When to Use This Skill

Activate this skill when:

• Understanding consensus fundamentals
• Implementing distributed agreement
• Building fault-tolerant systems
• Understanding Google Chubby, Spanner
• Comparing with RAFT
• Studying distributed systems theory
• Building replicated state machines
• Designing coordination services

Core Concepts

Paxos Overview

Goal: Achieve agreement on single value among distributed nodes despite failures

Key properties:

• Safety: Only one value chosen
• Liveness: Eventually chooses value (if majority available)
• Fault tolerance: Tolerates f failures with 2f+1 nodes

Roles (nodes can have multiple roles):

Proposer  → Proposes values
Acceptor  → Votes on proposals
Learner   → Learns chosen value

---

Basic Paxos

Two Phases

Phase 1: Prepare

Proposer → Acceptors: PREPARE(n)
Acceptors → Proposer: PROMISE(n, accepted_value)

Phase 2: Accept

Proposer → Acceptors: ACCEPT(n, value)
Acceptors → Learners: ACCEPTED(n, value)

Algorithm Details

class Proposer:
    def __init__(self, node_id, acceptors):
        self.node_id = node_id
        self.acceptors = acceptors
        self.proposal_number = 0

    def propose(self, value):
        """Propose a value using Basic Paxos"""
        # Generate unique proposal number (node_id + counter)
        self.proposal_number += 1
        n = (self.proposal_number, self.node_id)

        # Phase 1: Prepare
        promises = []
        for acceptor in self.acceptors:
            response = acceptor.prepare(n)
            if response:
                promises.append(response)

        # Need majority
        if len(promises) < len(self.acceptors) // 2 + 1:
            return None  # Failed to get majority

        # Use highest-numbered accepted value, or our value if none
        accepted_values = [p for p in promises if p.accepted_value is not None]
        if accepted_values:
            # Must use previously accepted value
            value = max(accepted_values, key=lambda x: x.accepted_n).accepted_value

        # Phase 2: Accept
        accepts = 0
        for acceptor in self.acceptors:
            if acceptor.accept(n, value):
                accepts += 1

        # Chosen if majority accepted
        if accepts >= len(self.acceptors) // 2 + 1:
            return value

        return None  # Failed


class Acceptor:
    def __init__(self):
        self.promised_n = None      # Highest n seen in prepare
        self.accepted_n = None       # Highest n accepted
        self.accepted_value = None   # Value accepted with accepted_n

    def prepare(self, n):
        """Phase 1: Prepare"""
        # Promise not to accept proposals < n
        if self.promised_n is None or n > self.promised_n:
            self.promised_n = n
            return Promise(n, self.accepted_n, self.accepted_value)
        return None  # Reject (n too low)

    def accept(self, n, value):
        """Phase 2: Accept"""
        # Accept if n >= promised_n
        if self.promised_n is None or n >= self.promised_n:
            self.promised_n = n
            self.accepted_n = n
            self.accepted_value = value
            return True
        return False  # Reject (n < promised_n)


class Promise:
    def __init__(self, n, accepted_n, accepted_value):
        self.n = n
        self.accepted_n = accepted_n
        self.accepted_value = accepted_value

---

Multi-Paxos

Optimization for Multiple Values

Basic Paxos: Requires two round-trips per value (expensive!)

Multi-Paxos: Elect stable leader, skip Phase 1 for subsequent proposals

class MultiPaxos:
    def __init__(self, nodes):
        self.nodes = nodes
        self.leader = None
        self.log = []  # Sequence of chosen values

    def elect_leader(self):
        """One-time leader election using Basic Paxos"""
        self.leader = self.run_basic_paxos_for_leader()

    def propose_value(self, value):
        """Leader proposes value (skips Phase 1)"""
        if not self.leader or self.leader != self.node_id:
            raise NotLeaderError()

        # Leader can skip Phase 1 (already has promises)
        # Phase 2 only: Accept
        log_index = len(self.log)
        accepts = 0
        for acceptor in self.acceptors:
            if acceptor.accept_at_index(log_index, self.leader_n, value):
                accepts += 1

        if accepts >= len(self.acceptors) // 2 + 1:
            self.log.append(value)
            return True

        return False

---

Paxos vs RAFT

| Feature | Paxos | RAFT | |---------|-------|------| | Understandability | Complex, hard to grasp | Designed to be understandable | | Leader | Optional (Multi-Paxos adds leader) | Always has leader | | Log structure | Can have gaps | Contiguous log | | Membership changes | Challenging | Built-in mechanism | | Implementation | Many variations | Canonical algorithm | | Performance | Comparable | Comparable | | Adoption | Google (Chubby, Spanner) | etcd, Consul, more common |

---

Real-World Implementations

Google Chubby

Description: Distributed lock service using Paxos

# Conceptual Chubby API
class Chubby:
    def __init__(self, paxos_cluster):
        self.paxos = paxos_cluster

    def acquire_lock(self, lock_name, timeout=60):
        """Acquire distributed lock"""
        # Use Paxos to agree on lock holder
        value = {
            'holder': self.client_id,
            'timestamp': time.time(),
            'timeout': timeout
        }

        success = self.paxos.propose(f'/locks/{lock_name}', value)
        return success

    def release_lock(self, lock_name):
        """Release distributed lock"""
        self.paxos.propose(f'/locks/{lock_name}', None)

Google Spanner

Description: Globally-distributed database using Paxos for replication

Paxos groups: Each shard replicated via Paxos

Shard 1:  Paxos(Replica A, B, C)
Shard 2:  Paxos(Replica D, E, F)
Shard 3:  Paxos(Replica G, H, I)

Transactions: Two-phase commit across Paxos groups

---

Practical Implementation

Python Example

import time
import random
from typing import Optional, Tuple

class PaxosNode:
    """Complete Paxos node (proposer + acceptor + learner)"""

    def __init__(self, node_id, all_nodes):
        self.node_id = node_id
        self.all_nodes = all_nodes

        # Proposer state
        self.proposal_id = 0

        # Acceptor state
        self.promised_id = None
        self.accepted_id = None
        self.accepted_value = None

        # Learner state
        self.learned_value = None

    def generate_proposal_id(self):
        """Generate unique, monotonically increasing proposal ID"""
        self.proposal_id += 1
        return (self.proposal_id, self.node_id)

    def propose(self, value):
        """Propose a value (Phase 1 + Phase 2)"""
        proposal_id = self.generate_proposal_id()

        # Phase 1: Prepare
        promises = []
        for node in self.all_nodes:
            response = node.receive_prepare(proposal_id)
            if response:
                promises.append(response)

        # Check majority
        if len(promises) < len(self.all_nodes) // 2 + 1:
            return False  # No majority, retry later

        # Determine value to propose
        highest_accepted = max(
            [p for p in promises if p[1] is not None],
            key=lambda x: x[0],
            default=(None, None)
        )

        if highest_accepted[1] is not None:
            value = highest_accepted[1]  # Must use existing value

        # Phase 2: Accept
        accepts = 0
        for node in self.all_nodes:
            if node.receive_accept(proposal_id, value):
                accepts += 1
                # Learner: Learn value when accepted
                node.learned_value = value

        return accepts >= len(self.all_nodes) // 2 + 1

    def receive_prepare(self, proposal_id):
        """Acceptor: Receive prepare request"""
        if self.promised_id is None or proposal_id > self.promised_id:
            self.promised_id = proposal_id
            return (self.accepted_id, self.accepted_value)
        return None

    def receive_accept(self, proposal_id, value):
        """Acceptor: Receive accept request"""
        if self.promised_id is None or proposal_id >= self.promised_id:
            self.promised_id = proposal_id
            self.accepted_id = proposal_id
            self.accepted_value = value
            return True
        return False

# Usage
nodes = [PaxosNode(i, []) for i in range(5)]
for node in nodes:
    node.all_nodes = nodes

# Multiple proposers competing
nodes[0].propose("value_A")
nodes[1].propose("value_B")

# Eventually one value wins
for node in nodes:
    print(f"Node {node.node_id} learned: {node.learned_value}")

---

Common Issues

Issue 1: Dueling Proposers

Problem: Two proposers keep interfering with each other

Proposer A: PREPARE(1)
Proposer B: PREPARE(2)  ← Invalidates A's prepare
Proposer A: PREPARE(3)  ← Invalidates B's prepare
Proposer B: PREPARE(4)  ← Invalidates A's prepare
... (infinite loop)

Solution: Randomized backoff or leader election (Multi-Paxos)

def propose_with_backoff(self, value):
    """Propose with exponential backoff"""
    backoff = 0.1
    max_attempts = 10

    for attempt in range(max_attempts):
        if self.propose(value):
            return True

        # Exponential backoff with jitter
        time.sleep(backoff * (1 + random.random()))
        backoff = min(backoff * 2, 10)

    return False

Issue 2: Learning the Chosen Value

Problem: Acceptors don't know when value is chosen

Solutions:

Option 1: Proposer notifies learners after Phase 2

def notify_learners(self, value):
    for learner in self.learners:
        learner.learn(value)

Option 2: Acceptors notify distinguished learner

def receive_accept(self, proposal_id, value):
    if self.accept_proposal(proposal_id, value):
        self.distinguished_learner.notify_accepted(proposal_id, value)

Option 3: Learners track acceptances

class Learner:
    def __init__(self, quorum_size):
        self.acceptances = {}  # proposal_id → {acceptor_ids}
        self.quorum_size = quorum_size

    def notify_accepted(self, acceptor_id, proposal_id, value):
        if proposal_id not in self.acceptances:
            self.acceptances[proposal_id] = (value, set())

        self.acceptances[proposal_id][1].add(acceptor_id)

        if len(self.acceptances[proposal_id][1]) >= self.quorum_size:
            self.learned_value = value

---

Testing Paxos

import unittest

class TestPaxos(unittest.TestCase):
    def test_single_proposer(self):
        """Single proposer should succeed"""
        nodes = [PaxosNode(i, []) for i in range(5)]
        for node in nodes:
            node.all_nodes = nodes

        result = nodes[0].propose("value_A")
        self.assertTrue(result)

        # All nodes should learn the value
        for node in nodes:
            self.assertEqual(node.learned_value, "value_A")

    def test_concurrent_proposers(self):
        """Concurrent proposers should reach consensus"""
        nodes = [PaxosNode(i, []) for i in range(5)]
        for node in nodes:
            node.all_nodes = nodes

        # Multiple proposers
        nodes[0].propose("value_A")
        nodes[1].propose("value_B")

        # All nodes should agree (on one of the values)
        learned_values = {node.learned_value for node in nodes if node.learned_value}
        self.assertEqual(len(learned_values), 1)  # All same

    def test_node_failure(self):
        """Should tolerate minority node failures"""
        nodes = [PaxosNode(i, []) for i in range(5)]
        for node in nodes:
            node.all_nodes = nodes

        # Simulate 2 nodes failing (3/5 still available)
        available_nodes = nodes[:3]

        # Proposal should still succeed with majority
        result = available_nodes[0].propose("value_A")
        self.assertTrue(result)

---

Performance Optimizations

1. Fast Paxos

Optimization: Skip proposer, clients send directly to acceptors

Benefit: One fewer network round-trip when no conflicts

2. Pipelining

Optimization: Proposer sends multiple proposals without waiting

Benefit: Higher throughput

3. Batching

def propose_batch(self, values):
    """Propose multiple values in single Paxos instance"""
    batch_value = {
        'type': 'batch',
        'values': values
    }
    return self.propose(batch_value)

---

Related Skills

• distributed-systems-consensus-raft - Alternative consensus algorithm
• distributed-systems-leader-election - Leader election patterns
• distributed-systems-distributed-transactions - Transaction protocols
• distributed-systems-replication-strategies - Data replication

---

Last Updated: 2025-10-27