Course contentsShow
← Software Engineering
Lesson 1418 of 1,93341. Scalability and Distributed SystemsFree lesson

The Paxos Algorithm

Understanding Paxos as a fault-tolerant consensus algorithm that tolerates node failures but not partitions.

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.