Skip to content

PATTERN Cited by 1 source

Version per request to resolve conflicts

Intent

Attach a totally-ordered, time-based version to every in-flight request in a consensus system so that a later elector encountering multiple conflicting incomplete requests can pick the correct one unambiguously — and so that propagating an old request through a new elector is itself distinguishable from the original.

Motivation

The concepts/request-propagation concern in consensus has seven distinct failure modes that no single-boolean "is this request durable?" query can resolve. Sugu Sougoumarane canonicalises the resolution as a single mechanism applied uniformly:

"It is safe to propagate the latest discovered decision. A decision to propagate a previous decision is a new decision." (Source: sources/2026-04-21-planetscale-consensus-algorithms-at-scale-part-7-propagating-requests)

The four-step protocol

  1. Every request has a time-based version.
  2. A leader creates a request using a newer version than any previous request.
  3. An elector propagating an incomplete request does so under a new version — not the original.
  4. An elector discovering multiple conflicting requests chooses the latest version.

The subtle and load-bearing rule is step 3: the propagated request becomes a new decision with its own version, so subsequent cascading propagations stay orderable. Under this rule, two elector-propagations of the same old request are distinguishable from each other and from the original.

Soundness

  • Newer-wins is safe: if two conflicting requests exist, the newer one's existence proves the older one never completed — because a durable older request would have been discovered by the elector that installed the newer one.
  • Propagation re-earns durability: the propagated request must satisfy durability under its new version; if propagation fails, a later elector sees the original-version incomplete state alone, not the propagated-version incomplete state.

Completed requests don't need versioning

Once a request is known durable + complete, no later elector will conflict with it. Only incomplete requests need the tag. This is the concrete efficiency payoff of separating completion and propagation concerns.

Canonical implementations

Substrate Version mechanism
Paxos Proposal numbers
Raft Leadership term numbers
MySQL replication GTID (leader identity + counter) + wall-clock timestamp
Systems with external lock Leadership epoch + per-request sequence
Systems with tight clocks Hybrid logical clock / Lamport timestamp

Consequences

  • Mandatory on-wire versioning layer: every request and every propagation carries a version; no lightweight "just write the value" path.
  • Total-order requirement on versioning mechanism: any two requests' versions must be comparable; this drives the choice of mechanism (Paxos's counter + node-id tuple, Raft's term number, MySQL's GTID-plus-timestamp).
  • Completion signalling becomes a separable concern: completed requests can drop their versions; only the incomplete-request subset carries the tag.
  • Anti-flapping makes this pattern optional in practice for large-scale MySQL-like deployments: if successor leadership changes are rate-limited far enough apart, the seven failure modes the versioning rule exists to mitigate become vanishingly rare. "Versioning of in-flight requests is less important for such systems."

Relation to proposal-numbers-at-election-layer

This pattern reuses the same time-based versioning primitive that concepts/proposal-number applies at the election layer (newer-proposal-number elector wins) at the request layer (newer-version request supersedes conflicts). Some protocols (Raft) collapse both layers into one number; others can separate them (e.g., a lock-based system using etcd for the election lock and a distinct per-request sequence for propagation).

Seen in

Last updated · 347 distilled / 1,201 read