CONCEPT Cited by 2 sources

Proposal number¶

Definition¶

A proposal number is a totally-ordered, timestamp-like identifier attached to every leadership-change attempt in a lock-free consensus algorithm. Followers remember the highest proposal number they have seen for the revoke/establish protocol and reject any message with a lower number. This is the mechanism that implements "newest elector wins" — the defining invariant of the lock-free family.

Paxos calls them proposal numbers; Raft calls them term numbers. Sugu Sougoumarane's framing collapses them into a single concept for the taxonomic argument:

"In the case of a lock-free approach, the newest elector must win over an older one. This requires the algorithm to assign a time-based order to the electors that are racing with each other. In Paxos, these are referred to as proposal numbers. In Raft, these are known as term numbers. To facilitate reasoning, we can view these numbers as timestamps."

"The core of the lock-free approach is that the followers that accept an establishment or revocation request must remember the timestamp of the elector that issued the request and should reject requests with older timestamps." (Source: sources/2026-04-21-planetscale-consensus-algorithms-at-scale-part-5-handling-races)

Required properties¶

Total order: any two proposal numbers are comparable.
Monotonically increasing in time: later attempts produce larger numbers (by construction — typically max(seen) + 1 with a uniqueness bit).
Unique per elector: avoid collisions, typically via (counter, elector-id) tuple with lexicographic order or via leader-ID bits in the low part.

Convergence under two-elector race¶

Sugu's explicit two-branch convergence analysis:

"(1) The elector with the older timestamp completes its election before the one with the newer timestamp. Following this, the one with the newer timestamp will end up revoking that leadership and establishing its own. (2) The elector with the newer timestamps completes first. Then the one with the older timestamp will fail at its attempt, and the leadership established by the newer timestamp will prevail."

Either way, the newer-timestamp elector's leadership prevails. Forward progress is therefore intrinsic to the protocol — no timeouts needed.

The "revoke all potential candidates" safety rule¶

Proposal numbers alone are not sufficient to close the race between a slow old elector and a new one, so Sugu names the corresponding safety rule:

"To cover the above scenarios, every elector must assume that there may be another elector with an older timestamp attempting a leadership change. It must therefore attempt to revoke leadership from all potential candidates, not just the current known leader. The completion of this process ensures that all possible leaderships (present and future) with an older timestamp are invalidated. This addresses the case where an old elector is slow at performing its actions. This also adds safety against clock skews: a new leader with an incorrect older timestamp will just fail at completing a leadership change, as if it was an older leader."

The revoke-all-potential-candidates rule absorbs both the slow-predecessor case and the clock-skew case under a single safety invariant: a leader with a skewed-backward timestamp fails harmlessly as if it were "just" an older leader.

Relation to lock-based family¶

Under lock-based election, proposal numbers are not strictly needed for electing a leader — the lock itself picks the winner. Sugu notes:

"If you are using a lock-based approach, there is no need to use proposal numbers or leadership terms for the purpose of electing a leader. But we may still need to assign such a number to facilitate the propagation of requests. We will discuss this in a subsequent blog."

Proposal numbers can thus reappear in lock-based systems at the request-propagation layer rather than the election layer — the two concerns having been factored apart per the revoke-and-establish split.

Seen in¶

sources/2026-04-21-planetscale-consensus-algorithms-at-scale-part-7-propagating-requests — canonical wiki extension of proposal numbers from the election layer (Part 5: newer-proposal-number elector wins the race) to the request layer (Part 7: newer-version request supersedes conflicts during propagation). Sugu closes the explicit forward-reference he made in Part 5: "If you are using a lock-based approach, there is no need to use proposal numbers or leadership terms for the purpose of electing a leader. But we may still need to assign such a number to facilitate the propagation of requests. We will discuss this in a subsequent blog." Part 7 is that blog. The generalised concept at the request layer is canonicalised as concepts/request-versioning; proposal numbers and term numbers are two canonical implementations of request versioning, alongside MySQL GTID + timestamp. Same mechanism, two different layers.
sources/2026-04-21-planetscale-consensus-algorithms-at-scale-part-5-handling-races — canonical wiki unification of Paxos proposal numbers and Raft term numbers as a single proposal number concept, the core of lock-free leader election, with the revoke-all-potential-candidates safety rule named explicitly.