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.