Course contentsShow
← System Design
Lesson 611 of 1,91917. Consensus AlgorithmsFree lesson

Proposal Numbers and Ordering

Why globally unique, monotonically increasing proposal numbers prevent conflicts and ensure progress.

Proposal Numbers and Ordering

What You'll Learn

You'll discover why globally unique, monotonically increasing proposal numbers are the secret weapon that keeps Paxos from descending into chaos.

The Core Problem

In Paxos, multiple proposers might try to get their values accepted simultaneously. Without coordination, they could endlessly interfere with each other, preventing any progress. Think of it like an auction where multiple auctioneers shout bids at the same time—chaos!

How Proposal Numbers Solve This

Every proposal in Paxos carries a unique, monotonically increasing number. These numbers establish a clear ordering: higher proposal numbers always win over lower ones.

Here's the magic:

Preventing Conflicts

When an acceptor sees a proposal with number N, it promises to ignore any future proposals with numbers less than N. This creates a "ratchet effect"—once you've seen proposal 42, you won't entertain proposal 41. Conflicts dissolve because there's always a clear winner.

Ensuring Progress

If a proposer's attempt fails (perhaps another proposer interfered), it simply tries again with a higher proposal number. Eventually, one proposer gets far enough ahead that its proposal completes before others can interfere. No permanent deadlock.

Uniqueness Matters

Proposal numbers must be globally unique, often achieved by combining a sequence number with the proposer's ID (e.g., sequence_100_proposerA). This ensures no two proposers ever use the same number, preventing ambiguous orderings.

The Auction Analogy

Imagine each proposer has a numbered paddle. You can only bid with a paddle number higher than the last accepted bid. Eventually, someone gets a high enough number that their bid wins before anyone can outbid them.

Key Takeaway: Globally unique, monotonically increasing proposal numbers create unambiguous ordering that prevents conflicts and guarantees at least one proposer can eventually make progress—the foundation of Paxos's correctness.