Deep Dive: Paxos Explained

The Patriarch of Provable Consensus

Paxos, conceived by Leslie Lamport in the 1980s (though published later), stands as a landmark achievement in distributed systems. It is a family of protocols for solving consensus in a network of unreliable processors (nodes). Its significance lies in being one of the first algorithms proven to be correct for achieving agreement in asynchronous systems prone to crash failures (but not Byzantine failures). Despite its reputation for being difficult to understand, its principles have influenced many subsequent consensus algorithms and distributed systems designs.

As we previously discussed, achieving agreement is non-trivial. Paxos provides a formal framework to do so.

Core Concepts in Paxos

Paxos operates using a set of roles that processes can take on, and it proceeds in rounds. Key concepts include:

• Roles:
  • Proposers: Nodes that suggest values to be agreed upon.
  • Acceptors: Nodes that can accept proposed values. A majority of acceptors must agree for a value to be chosen.
  • Learners: Nodes that learn the chosen value once consensus is reached. In practice, roles are often combined; a node can be a Proposer, Acceptor, and Learner.
• Proposal Numbers (Rounds): Each proposal is associated with a unique, increasing proposal number. This is crucial for ordering and ensuring progress.
• Quorums: Paxos requires a majority of acceptors (a quorum) to agree on a proposal for it to be chosen. This ensures that even if some acceptors fail, consensus can still be reached.

The Paxos Protocol (Simplified)

The basic Paxos protocol (often called "Single-Decree Paxos" as it decides on one value) typically involves two main phases for a given proposal round:

Phase 1: Prepare/Promise

1. Prepare Request: A Proposer chooses a new proposal number *n* and sends a "prepare" request with *n* to a majority of Acceptors. Proposer -> Acceptors: prepare(n)
2. Promise Response: An Acceptor receives the prepare request. If *n* is greater than any proposal number it has already responded to in a promise, it promises not to accept any more proposals numbered less than *n*. If it had already accepted a proposal, it includes that proposal's number and value in its response. Acceptor -> Proposer: promise(n, [previously_accepted_proposal_number, previously_accepted_value])

Phase 2: Propose/Accepted

1. Propose Request (Accept!): If the Proposer receives promises from a majority of Acceptors:
   • It chooses a value *v*. If any Acceptors reported a previously accepted value, the Proposer must choose the value associated with the highest proposal number among those reported. Otherwise, it can choose its own proposed value.
   • It then sends an "accept!" request with the chosen proposal number *n* and value *v* to the same majority of Acceptors. Proposer -> Acceptors: accept!(n, v)
2. Accepted Response: An Acceptor receives the accept! request. If it has not already promised to consider only proposals greater than *n*, it accepts the proposal (n,v) and notifies Learners. Acceptor -> Learners: accepted(n, v)

A value is considered chosen (consensus reached) when a majority of Acceptors have accepted it. Learners find out about the chosen value either by hearing from Acceptors or through other Learners.

Strengths of Paxos

• Provably Correct: Its core strength is its mathematical proof of correctness for crash-fault tolerance.
• Fault Tolerance: Can tolerate failures of f nodes as long as a majority (f+1 out of 2f+1) remain operational and can communicate.
• Asynchronous Safety: Guarantees safety (agreement and validity) even in purely asynchronous environments where message delays are unbounded (though liveness might be affected).

Challenges and Complexities

• Understandability: Lamport's original presentation was notoriously difficult. Even simplified explanations can be challenging.
• Liveness: In certain scenarios with dueling proposers, basic Paxos can suffer from liveness issues where no proposal gets a majority (though this is often addressed with leader election in practical implementations).
• Performance: The two-phase commit can introduce latency. Optimizations are often needed for high-throughput systems.
• Multi-Paxos: Basic Paxos decides on a single value. For a sequence of values (like a log), Multi-Paxos is used, which typically involves electing a stable leader to optimize the protocol by skipping Phase 1 for subsequent proposals from the same leader. This makes it much more practical. Many system designs, like those found in Understanding Microservices Architecture, often rely on such underlying consensus for coordination services.

Despite its complexities, Paxos laid the groundwork for many distributed systems. Its sibling algorithm, Raft, was later designed with understandability as a primary goal, addressing one of Paxos's main criticisms.

Further exploration into how systems ensure reliability can be found in topics such as Chaos Engineering, which tests the resilience Paxos aims to provide.