Course contentsShow
← Computer Science
Lesson 2674 of 2,87259. Consensus and ReplicationFree lesson

Proposal Numbers and Ordering

Understanding how unique, totally-ordered proposal numbers enable progress and prevent conflicts in Paxos.

Proposal Numbers and Ordering

What you'll learn: How Paxos uses unique, totally-ordered proposal numbers to ensure progress and prevent conflicting decisions in distributed consensus.

The Problem of Multiple Proposals

In Paxos, multiple proposers might try to get different values accepted simultaneously. Without a way to distinguish and order these competing proposals, the system could deadlock or accept conflicting values. This is where proposal numbers become critical.

What Are Proposal Numbers?

A proposal number is a unique identifier attached to every proposal sent by a proposer. These numbers have two essential properties:

  1. Uniqueness: No two proposals ever share the same number
  2. Total ordering: Any two proposal numbers can be compared (n₁ < n₂ or n₁ > n₂)

How Ordering Enables Progress

Think of proposal numbers like bidding in an auction. Each new bid must be higher than the last. In Paxos:

  • Acceptors reject proposals with numbers they've already seen or exceeded
  • Acceptors consider proposals with higher numbers than any seen before
  • Proposers can always generate a higher number to "outbid" others

This ordering ensures that even when proposals compete, the system can make forward progress—a proposer can always try again with a higher number.

Generating Unique Numbers

A common scheme: combine a counter with the proposer's unique ID:

proposal_number = (round_counter << 16) | proposer_id

This guarantees both uniqueness (different IDs) and that each proposer can generate strictly increasing numbers.

Preventing Conflicts

When an acceptor receives a proposal with number N, it promises not to accept any future proposals numbered less than N. This "promise to ignore the past" prevents older, stale proposals from interfering with newer ones, ensuring the system converges on a single decision.

Key Takeaway: Proposal numbers provide a total ordering that allows Paxos to resolve competition between proposers, ensure progress through higher-numbered retries, and prevent conflicts by making acceptors ignore outdated proposals.