Skip to content

CONCEPT Cited by 1 source

Incomplete request

Definition

An incomplete request is a request for which the elector (during a leadership change) cannot determine whether the old leader had made it durable. It is the central concept around which the seven propagation failure modes are organised in Sugu Sougoumarane's Part 7 of Consensus algorithms at scale. The elector's knowledge is structurally incomplete — it cannot reach every follower of the old leader, so it cannot observe the complete durability state of every in-flight request.

Three request lifecycle states

Sugu's framing implicitly divides requests into three states relevant to a leadership-change elector:

  1. Complete + durable — the elector is guaranteed to find these. "An elector is guaranteed to find all requests that have become durable." This follows from the construction: the elector's fencing threshold and the durability threshold overlap, so reaching enough followers to revoke the old leader also means reaching at least one follower of every durable request.

  2. Incomplete, not discovered — the elector didn't find the request. "If a request was incomplete, an elector may not find it. If not found, it is free to move forward without that request. When that request is later discovered, it must be canceled." Safe to drop; must cancel if rediscovered.

  3. Incomplete, discovered — the elector found the request but cannot tell if it was durable. "If an elector discovers an incomplete request, it may not have sufficient information to know if that request was actually durable or complete. Therefore, it has to assume that it might have completed, and attempt to propagate it." Must treat as tentative and propagate under a new version.

(Source: sources/2026-04-21-planetscale-consensus-algorithms-at-scale-part-7-propagating-requests)

The edge case: certain-incomplete

A fourth sub-case: an elector may discover an incomplete request and determine with certainty that it was incomplete (e.g., by observing a follower in a pre-completion state that could only occur if durability was not yet met). Sugu's rule:

"If an elector discovers an incomplete request and can determine with certainty that it was incomplete, it can choose either option: act as if it was discovered, or not discovered."

Either choice is safe because the certainty gives the elector enough information to decide without creating downstream conflict.

Why incomplete requests are hard

The hard case is incomplete-discovered — the elector cannot distinguish a request that was about to become durable under the old leader from one that was nowhere near durability. The resolution is to assume durability might have been achieved and propagate the request under a new version; see concepts/request-versioning for the versioning mechanism and patterns/version-per-request-to-resolve-conflicts for the pattern.

The seven failure modes revisited

The failure-mode enumeration Sugu gives in Part 7 is an interaction matrix between:

  • Elector knowledge: complete vs partial discovery of incomplete requests
  • Request lifecycle: incomplete vs tentative vs durable
  • Protocol step: discovery vs propagation vs marking-complete

The seven failure modes are all distinct combinations of these three axes. The central organising fact: no single-boolean query resolves any of them individually; the protocol must encode richer state (request version, leader identity, timestamp) to make downstream electors able to untangle the history.

Seen in

Last updated · 347 distilled / 1,201 read