Skip to content

CONCEPT Cited by 2 sources

Request propagation

Definition

Request propagation is the concern of surfacing requests that were durable under a prior leader onto the new leader's follower set during a leadership change, so that the new leader meets its durability criterion without losing completed work. Sugu Sougoumarane canonicalises it as the load-bearing final concern of consensus — the concern the whole framework (durability redefinition, revoke/establish, race handling, request completion) exists to make possible:

"We have saved the most difficult part for last. This is where we put it all together. Let us start with a restatement of the requirements for propagation of requests during a leadership change: Propagate previously completed requests to satisfy the new leader's durability requirements." (Source: sources/2026-04-21-planetscale-consensus-algorithms-at-scale-part-7-propagating-requests)

If propagation is wrong, a completed request can be lost across a failover — the single failure mode the entire consensus framework exists to prevent.

Two regimes

Planned-change regime (graceful)

The current leader is reachable, so it can ensure its requests have reached the new leader's required followers before stepping down:

"For lock-based systems, and for planned changes, we have the opportunity to request the current leader to demote itself. In this situation, the current leader could ensure that its requests have reached all the necessary followers before demoting itself. Once this is done, the elector performs the leadership change and the system can resume."

This is the easy case. The leader satisfies the new durability requirement before the hand-off happens. See patterns/graceful-propagation-before-demotion.

Failure regime

The current leader is unreachable, so the elector indirectly revokes leadership by fencing enough followers that the old leader can no longer meet its durability criterion:

"If a system has encountered failures, then the elector must indirectly revoke the previous leadership by requesting the followers to stop accepting any more requests from that leader. If enough followers are reached such that the previous leader cannot meet the durability criteria for any more requests, we know that the revocation is successful."

The fencing process simultaneously exposes previously-completed requests: "This method, apart from guaranteeing that no further requests will be completed by that leader, also allows us to discover all requests that were previously completed."

Revocation and discovery share a primitive

A canonical wiki design datum: the failure-driven propagation pathway composes revocation and discovery into one protocol step rather than running two separate ones. Reaching a sufficient set of followers to prevent the old leader from meeting durability is the same operation as discovering every request the old leader durably completed — by definition, every durable request has at least one follower in the reached set (durability threshold ≤ revocation threshold). Raft and Paxos both exploit this composition; the majority-quorum proposal is revocation-plus-discovery-in-one.

The seven failure modes

Even with the fencing primitive, Sugu enumerates seven distinct interactions between elector knowledge and request lifecycle that make propagation "not as simple as it sounds":

  1. A request may be incomplete; the elector may or may not discover it.
  2. A discovered tentative request may or may not be durable; the elector cannot distinguish.
  3. Propagation itself can fail before completion.
  4. An elector that misses an incomplete request can elect a new leader that accepts a new conflicting request that also fails before completion.
  5. A subsequent elector can then discover multiple incomplete conflicting requests.
  6. An elector can propagate one as tentative and fail before marking it complete.
  7. A final elector can discover both a durable propagated request and a newer incomplete conflicting one and have insufficient information to pick correctly.

No single-boolean "is this request durable?" query can resolve the space. The protocol must carry sufficient on-wire state. See concepts/incomplete-request for the request-lifecycle detail and concepts/request-versioning for the resolution primitive.

Resolution: time-based versioning

The mitigation is a single rule: every request carries a time-based version, and later versions supersede earlier ones — including when an elector propagates an old request (which assigns it a new version rather than preserving the original). See concepts/request-versioning for the four-step protocol and patterns/version-per-request-to-resolve-conflicts for the pattern.

Production shortcut: anti-flapping

Large-scale systems rely on concepts/anti-flapping rules that rate-limit leadership changes, which serendipitously also mitigate the seven failure modes by preventing rapid successor-elections from racing each other. "Versioning of in-flight requests is less important for such systems." This is how MySQL-at-massive-scale (via Orchestrator and Vitess's VTOrc fork) avoids split-brain despite MySQL binlog's faithful-GTID-propagation breaking the strict per-version-on-every-new-decision rule.

Seen in

Last updated · 347 distilled / 1,201 read