Skip to content

CONCEPT Cited by 1 source

Two-phase completion protocol

Definition

The two-phase completion protocol is the consensus-commit shape in which a leader first transmits a request to followers as tentative and — only after durability is met — sends a second message instructing followers to complete (materialise) it. The protocol makes the request lifecycle explicit across three stages (incomplete, durable, complete) with a mutual-exclusion invariant between completion and cancellation.

Sugu Sougoumarane's canonical wiki framing: "The above requirements can be met by introducing a two-phase protocol. The leader first transmits the payload of the request as tentative to all the nodes. A tentative request is one that can later be completed or canceled. A follower that is responsible for a leader's durability should acknowledge receipt of tentative requests. Once the leader receives the necessary acknowledgements from its followers, the request has become durable and cannot be canceled. The leader can then issue messages to complete the tentative request." (Source: sources/2026-04-21-planetscale-consensus-algorithms-at-scale-part-6-completing-requests).

Not the same as two-phase commit

Despite the name, this is not two-phase commit (the transactional-atomicity protocol). The shape is similar — one prepare-like phase, one commit-like phase — but the invariants differ:

  • Two-phase commit (2PC) — cross-participant atomicity: either all participants apply, or none do.
  • Two-phase completion — single-write durability: a request is never forgotten after ack, and never applied before durable.

A consensus system built on two-phase completion can of course also run 2PC for cross-shard atomicity on top, but the two mechanisms are doing different jobs at different altitudes.

The three stages

Stage Leader knows Followers know Cancelable? Effect applied?
Incomplete acks not sufficient tentative marker yes no
Durable (implicit) acks sufficient tentative marker (no change) no no
Complete complete sent applied n/a yes

The transition from incomplete → durable is implicit: no new message is sent, no follower-side marker changes. Durability is a property of the system-wide state, known only to the leader once it has tallied enough acks.

The mutual-exclusion invariant

"Completion and cancellation are mutually exclusive: A request that was completed will never be canceled, and a request that was canceled will never be completed."

This is the canonical safety property of the protocol. Clients can rely on this when composing their own idempotency / retry logic: a request that received a success ack is not going to be quietly reverted later.

Leader-side retry discipline

If the leader cannot reach durability (not enough followers are reachable, or acks are slow), it:

  • Must keep retrying. The request is in flight; abandoning it leaves a tentative record on some followers.
  • Must not cancel. Cancellation is the elector's prerogative during a leadership change; if the leader cancelled its own tentative request, a concurrent elector could still be trying to propagate it.

See concepts/forward-progress for the broader framing of retry-vs-cancel in consensus systems.

Why separation is valuable

A single-phase "send-and-apply" protocol (e.g. MySQL semi-sync) has no vocabulary for abandoned work. The follower cannot distinguish a received-but-not-yet-durable write from a durable one. On a leader crash + restart, the primary can complete writes that were never durable, producing semi-sync split-brain. The tentative marker is the affordance that plugs this hole.

Optimisation: skip tentative for lagging followers

Once a request is durable, sending tentative to a follower that has not yet received it is wasted work — the follower would ack, the leader would then send complete. Instead:

"Once a request becomes durable, the leader is free to transmit that request as complete to followers that have not yet received the message as a single step."

See patterns/skip-completion-for-late-followers for the pattern.

Trade-off: early-ack vs late-ack

The client-ack can happen at either the durable stage or the complete stage:

  • Early-ack (durable) — one round-trip saved; forces quorum reads unless a leader lease is in place.
  • Late-ack (complete) — two round-trips total; leader-local reads are trivially consistent.

Systems with lock-based leader election + stable leader lease can have the best of both: early-ack + leader-local consistent reads. Systems with lock-free leader election must pay the quorum-read tax if they want early-ack.

Seen in

Last updated · 347 distilled / 1,201 read