Understanding Paxos Made Simple

The challenge of achieving consensus in a distributed system is a fundamental problem in computer science. Leslie Lamport's 2001 paper, Paxos Made Simple, aims to distill the complex logic of the Paxos algorithm into a digestible format, ensuring that a group of unreliable processors can agree on a single value.

The Core Objective

The goal is to reach agreement on a value among a set of participants. The system must maintain Safety (nothing "bad" happens) and strive for Liveness (something "good" eventually happens).

Safety Definition: Only a single value is chosen, and if a value is chosen, it is the only value that can ever be chosen.

---

👥 Roles in the Ecosystem

In the Paxos protocol, nodes can take on different roles. A single physical server often performs all three roles simultaneously.

---

⚙️ The Protocol Logic

The algorithm operates in two primary phases. To ensure consistency, every proposal is tagged with a unique, monotonically increasing number n.

Phase 1: Prepare and Promise

1. Prepare: A Proposer selects a proposal number n and sends a prepare(n) message to a majority of Acceptors.
2. Promise: If an Acceptor receives a prepare(n) where n is greater than any proposal number it has already responded to, it:
   • Promises not to accept any future proposals numbered less than n.
   • Returns the value v of the highest-numbered proposal it has already accepted (if any).

Phase 2: Accept and Accepted

1. Accept Request: If the Proposer receives promises from a majority of Acceptors, it sends an accept(n, v) message.
   • Crucial Nuance: If any Acceptors returned a value v in Phase 1, the Proposer must use the value associated with the highest proposal number among the responses. Otherwise, it can pick its own value.
2. Accepted: An Acceptor accepts the proposal accept(n, v) unless it has already promised to a proposal number greater than n.

🛠 Implementation Logic (Pseudo-code)

class Acceptor:
    def __init__(self):
        self.promised_n = 0
        self.accepted_n = 0
        self.accepted_v = None

    def handle_prepare(self, n):
        if n > self.promised_n:
            self.promised_n = n
            return (True, self.accepted_n, self.accepted_v)
        return (False, None, None)

    def handle_accept(self, n, v):
        if n >= self.promised_n:
            self.promised_n = n
            self.accepted_n = n
            self.accepted_v = v
            return True
        return False

---

📉 Visualizing the Flow

The following diagram illustrates the interaction between the roles:

---

📐 Mathematical Foundations

The reliability of Paxos relies on the intersection of majorities. If we have a total of $N$ acceptors, a majority is defined as:

$\text{Majority} = \lfloor \frac{N}{2} \rfloor + 1$

Because any two majorities must overlap by at least one member, the "memory" of a chosen value is guaranteed to persist. If a value $v$ was chosen by a majority $M_1$, any subsequent proposer must contact a majority $M_2$. Since $M_1 \cap M_2 \neq \emptyset$, at least one acceptor in $M_2$ will inform the proposer about $v$ during the prepare phase.

---

⚠️ The Liveness Problem

While Paxos is safe, it can suffer from a "livelock" scenario.

Paxos always terminates quickly. $\rightarrow$ Incorrect.

If two proposers keep issuing higher proposal numbers (n+1, n+2, etc.) before the other can finish Phase 2, the system will loop forever.

The Solution: The Distinguished Proposer

To resolve this, the system typically elects a Distinguished Proposer (Leader).

• Elect a single leader.
• Leader handles all proposals.
• Other nodes forward requests to the leader.
• (Optional) Implement a timeout for leader failure.

---

🖼 System Architecture Overview

Summary of Constraints

• Network: Messages can be delayed, lost, or reordered, but not corrupted.
• Nodes: Nodes can crash and restart, but they must remember their promised_n and accepted_v (stable storage).
• Outcome: Once a majority accepts a value, that value is permanently chosen.