The Paxos Algorithm
What you'll learn: You'll understand how Paxos achieves consensus in distributed systems even when nodes fail (but not during network partitions).
Why Paxos Matters
After learning about Two-Phase Commit's blocking problems and Three-Phase Commit's complexity, you need a consensus algorithm that actually handles node failures gracefully. Paxos solves this by tolerating up to (N-1)/2 failed nodes while still reaching agreement on a single value.
The Core Idea
Paxos works like a parliamentary voting system with multiple rounds:
Imagine a committee trying to agree on a budget proposal. Even if some members are absent or slow to respond, the committee can still reach a decision as long as a majority (quorum) participates. Once a majority agrees, that decision is final—even if different proposals were initially suggested.
Paxos divides consensus into two phases:
Phase 1: Prepare
A proposer (like a committee member suggesting a value) sends a "prepare" request with a unique proposal number to acceptors (voters). If a majority responds positively, the proposer can proceed.
Phase 2: Accept
The proposer sends an "accept" request with the proposal to acceptors. If a majority accepts it, consensus is reached.
The clever part: Once a value is accepted by a majority, any future proposals must honor that value. This ensures safety—only one value is ever chosen, even across failures.
Limitations
Paxos assumes no network partitions. During a partition, multiple leaders might compete indefinitely without progress (a liveness problem). It also tolerates node crashes but not Byzantine failures (where nodes send malicious or corrupted messages).
Key Takeaway: Paxos is a foundational consensus algorithm that tolerates node failures through majority voting, guaranteeing that once a value is chosen by a quorum, it remains permanent—though it struggles with network partitions and requires careful implementation.