Distributed consensus, replication, and fault tolerance / personal lessonsLesson 14 of 17
Lesson browserDistributed consensus, replication, and fault tolerance lessonsPrevious: Recovery, snapshots, and membership changesNext: Leaderless replication and conflict-free data
Distributed systems · Lesson 14

Consensus is not a distributed transaction

Separate replicated decisions, atomic commit, isolation, and compensation.

By the end: Explain why correct per-shard replication does not make a cross-shard transfer atomic.

One log does not cover every partition

Suppose one consensus group stores account Ada and another stores account Bo. A transfer debits Ada by 10 and credits Bo by 10. Each group can replicate its own update correctly while the debit commits and the credit does not. The application invariant that the transfer preserves the total is a relationship across both groups.

Atomic commit asks whether all participating pieces commit or all abort. Isolation constrains how concurrent transactions observe and affect one another. Durability concerns survival of a completed decision under the promised failures. Consensus on a replicated coordinator’s decision can help an atomic-commit protocol survive coordinator crashes, but does not replace the participants’ prepare conditions, locking or validation, and recovery rules.

Define the transaction boundary before choosing a coordinator

A cross-shard transfer contains several decisions with different scopes. The Ada shard decides how its own replicated log advances. The Bo shard does the same independently. The transaction protocol decides whether the debit and credit belong to one committed transfer. Application code decides whether the transfer satisfies conditions such as sufficient funds. Agreement inside each shard cannot answer the last two questions merely because every shard uses a correct consensus algorithm. The relevant invariant relates state in both groups, while each individual log orders commands for only its own replicated state machine.

Use a separate paper example with Ada holding 50 and Bo holding 20. A transfer of 10 should produce 40 and 30, preserving a total of 70. If the debit becomes a completed transaction while the credit is rejected, the resulting 40 and 20 are not the intended transfer. Reversing the request order only changes the possible partial outcome. Crediting first can produce 50 and 30 before failure. Neither ordering joins two independent commit boundaries. A reliable client can retry, but without a durable transaction identity and recovery rule it still cannot infer which pieces completed from a timeout.

Atomic commit gives participating updates one commit-or-abort outcome. It does not require every disk or screen to change at the same physical instant. A participant may learn the decision later than another. Isolation and access rules must prevent that notification delay from exposing observations forbidden by the database's transaction contract. A raw inspection of participant storage during recovery can show one final record and one prepared record without proving that clients were allowed a partial committed transaction. Distinguish internal implementation states from the operations the service promises to external callers.

Before a participant can promise to commit, it must know what it is promising. The Ada shard may check that 10 is available and reserve the necessary update. The Bo shard must be able to apply its credit if commit follows. If a participant merely answers yes after an ordinary read, another transaction could change the relevant state before the decision arrives. Preparation must preserve enough data and concurrency protection to honor the promise after delays and restarts. The specific protections depend on the database's isolation algorithm, not on the coordinator's choice of a word for the final outcome.

A transaction identifier connects these records across messages. Repeated prepare or decision requests must refer to the same transaction, and a delayed message must not accidentally apply to unrelated new work that reused an identity. This resembles retry deduplication but concerns a protocol with durable intermediate states as well as a final result. In a paper trace, keep a separate row for each participant's transaction status and each participant's business data. That separation prevents prepared from being mistaken for successful client completion. It also makes the coordinator's durable decision distinguishable from the moment every participant has learned that decision.

Derive two-phase commit

In two-phase commit, a coordinator first asks participants to prepare. A participant that votes yes durably records enough state to fulfill a future commit and typically retains locks or other protections. If any participant votes no, the coordinator can decide abort. It may decide commit only after all required participants vote yes. It durably records the decision and communicates it to participants, who finish accordingly.

A prepared participant cannot simply abort on timeout. The coordinator may already have committed and told another participant, with only this participant’s reply delayed. Forgetting the prepare state would then produce a split outcome. Basic two-phase commit can block when the decision is unavailable. Replicating the coordinator through consensus improves decision availability while its quorum is reachable, but cannot guarantee progress under every partition or missing participant. Two-phase commit’s phases are not the two phases of Basic Paxos.

A yes vote survives uncertainty about the decision

The two phases of two-phase commit create different kinds of evidence. During preparation, each yes vote says that participant can carry out commit and will retain its prepared obligation. During decision, the coordinator chooses commit only after every required participant has prepared successfully. A majority of participant yes votes is not enough. If Ada and Bo both hold essential pieces of a transfer, Ada's yes cannot replace Bo's no. A replicated participant may internally need a quorum to preserve its yes vote, but that quorum counts replicas of one participant, not distinct transaction participants.

Suppose both shards prepare and the coordinator durably records commit. It sends commit to Ada, then crashes before Bo receives it. Ada completes the debit. Bo still has a prepared credit. From Bo's local evidence, another execution remains possible in which the coordinator never received Ada's yes and chose abort. Bo cannot distinguish these executions by waiting for its own timer to expire. Its timeout can trigger a recovery query, but cannot justify choosing whichever outcome would release local resources fastest. In the commit execution, unilateral abort would make the participants disagree.

The durable prepare record must therefore be sufficient after a process restart. If Bo restarts, sees no record of its earlier yes, and treats the credit as abandoned, it can violate the obligation the coordinator relied on. If the coordinator restarts after recording commit but forgets that decision, it can issue an inconsistent abort. Durability is needed on both sides of the protocol, but the records have different contents. The participant retains the promised work and transaction status. The coordinator retains the authoritative outcome and enough identity information to communicate it correctly.

Replicating the coordinator changes the failure that makes its decision unavailable. If its decision log remains accessible through a healthy consensus quorum, a new coordinator process can recover the recorded outcome and continue notification. That does not make a missing participant optional. Before commit is decided, every participant still needs to prepare. After commit is decided, an unavailable participant may delay completion of its local work. Losing access to the coordinator's own quorum can also prevent recovery of the decision. Replication improves decision availability under its assumptions rather than proving unconditional termination.

Distinguish message retries from new decisions as you read the model below. A repeated commit notification should cause a participant already committed to confirm the same outcome, not apply the debit twice. A repeated prepare should not create a second reservation of funds for the same transaction. Durable state transitions constrain these responses. The table shows one permitted ordering of preparation, decision, and partial notification. Its highlighted rows are a reading sequence, not a scheduler that explores crashes or validates an arbitrary transaction system. Additional executions in this section are paper cases, with their assumptions stated explicitly.

Work through the model

PhaseAda shardBo shardCoordinator
PrepareDurable yes; debit pendingDurable yes; credit pendingCollects votes
DecideStill preparedStill preparedDurably records COMMIT
Partial notificationCommits debitWaiting for decisionReply to Bo delayed

Stage 1 of 3. All stages remain visible for comparison.

Step 0 / 2
Bo cannot decide abort from silence after preparing. The durable commit decision already exists elsewhere.

Trace visibility separately from commit notification

In the displayed final row, the coordinator has recorded commit and Ada has received it, while Bo is waiting. The conclusion is that Bo must preserve its ability to commit. The row does not say that a client can read an ordinary old balance at Bo without waiting or applying transaction-specific read rules. If the intended contract is a serializable transfer, reads and writes must participate in an isolation mechanism that handles these intermediate states. Atomic commitment and client-visible isolation require related but distinct arguments. Neither follows from the visual fact that the coordinator's outcome cell says COMMIT.

For a separate locking example, let the prepared transfer retain write locks on both account records. A lock is a rule that delays conflicting operations until the holder releases it. If a reader requests Bo's locked balance before Bo learns the outcome, it may wait. Once Bo obtains commit, applies the credit, and releases the lock, the reader can continue under the database's isolation rules. This explains one cost of uncertainty. A prepared transaction can hold resources that unrelated operations need, so an unavailable decision can block more work than the original client request alone.

A contrasting implementation could use versions and validation rather than this exact locking schedule. It would need its own proof about which versions readers see and which concurrent transactions may commit. The example does not imply that every transaction system locks every read or keeps physical locks across all failures. The durable requirement is to retain the prepared obligation. The isolation requirement is to reject or delay histories that violate the selected contract. The implementation may encode these obligations in different records, but cannot omit them because its shards already replicate their logs.

Now inspect a paper history involving two doctors. Initially Ada and Bo are both on call. Transaction T reads both records and proposes setting Ada off call. Concurrent transaction U reads the same initial records and proposes setting Bo off call. Each transaction sees another doctor available, so each local application check passes. Their writes affect different records. If both commit from that shared snapshot, nobody remains on call. The invariant fails even if every participant agrees on each transaction's commit outcome and no update is lost during replication.

To see why serializability excludes that history, try both serial orders. If T completes first, U's later read sees Ada off call and must retain Bo under the stated application rule. If U completes first, T must retain Ada. There is no serial execution of those checks in which both turn themselves off. Preventing the concurrent outcome requires conflict detection or protection covering the dependency, including the records read to justify each update. Merely deduplicating transaction identifiers or collecting all yes votes does not add that missing condition. Strict serializability would additionally preserve real-time precedence between nonoverlapping completed transactions.

Isolation and business compensation

Even atomic commit does not automatically provide serializable execution. Two transactions can read a shared condition, update different rows, and jointly violate an invariant unless locking or validation prevents the problematic concurrent schedule. For example, two on-call doctors each see the other on call and each turn themselves off. Snapshot isolation may permit that write skew; serializable execution must prevent both transactions from completing in that way.

A saga instead divides work into committed steps with compensating actions when later steps fail. Compensation is a new business action, not a time reversal that erases observations. Refunding a payment does not mean no payment happened; another party may already have seen it. Sagas can suit workflows where intermediate states and compensation are acceptable. They cannot substitute for strict atomicity merely by renaming rollback as compensation.

Choose whether partial business progress is acceptable

Some workflows cannot reasonably hold every external activity in a prepared state. A booking process might reserve a room, charge a payment method, and request a transport service from independent providers. Those providers may expose ordinary APIs rather than a common atomic-commit protocol. A local database can atomically record that a transport request should be sent. It cannot force the transport provider to undo a completed ride or preserve an uncommitted promise merely by adding that request to its own consensus log. The external service's API defines which guarantees are available at that boundary.

A saga makes the permitted intermediate states explicit. In a constructed workflow, room reservation succeeds first. Payment then succeeds. If transport fails, the application requests a refund and cancellation. Refund and cancellation are new operations with their own identities, failure modes, and responses. They may need retry and durable deduplication. A refund request that times out has an unknown outcome just like the original charge. Treating compensation as infallible would repeat the same mistake that motivated transaction recovery in the first place.

Compensation can restore a chosen business condition without restoring the original world. The final financial balance may match its starting value after a charge and refund, while the customer still saw a temporary charge and the provider incurred processing work. A released room may already have become unavailable to another customer during the reservation interval. These observations distinguish compensation from an atomic abort in which the transaction never committed its effects. A saga is appropriate only if the application contract accepts the intermediate commitments and specifies what happens when compensation is delayed or cannot complete.

A useful design comparison starts with the invariant rather than protocol names. If a transfer must never be presented as only a debit or only a credit, define a transactional boundary and an isolation contract that enforce that requirement. If a booking may remain pending while independent providers respond, represent pending as a durable business state. Do not label pending as fully confirmed and then rely on later compensation to make the earlier promise accurate. The state machine should distinguish confirmed, rejected, and unresolved work so clients know which decisions are final and which may still change.

Finally, examine cleanup as another recovery action. A coordinator cannot safely forget a decision while a prepared participant may still need it, unless the protocol has another way to resolve that participant's obligation. Similarly, a workflow cannot discard a compensation task merely because its original client disconnected. Retained decision records, acknowledgments, and retry rules define when work is complete enough to reclaim. Their exact lifetime depends on the chosen protocol. This lesson derives the information they must preserve; it does not provide a general database validator or a complete implementation of distributed commit. The existing exercises test the distinction between local replicated success and a transaction-wide guarantee.

Exercises

A prepared shard times out

A participant has durably voted yes but cannot reach the coordinator. Why not abort immediately and release its locks?

Hint

Imagine another participant has already received commit.

Worked answer
Possible worldOther participantSafe local inference from silence
Coordinator abortedWill abortUnknown
Coordinator committedMay already commitUnknown
The same local silence does not identify the global decision.

The coordinator may already have decided commit. Unilateral abort would then violate atomicity. The participant needs a safe recovery path to discover the decision or evidence that abort is allowed under the protocol. Waiting is a liveness cost paid to avoid an inconsistent outcome.

Two consensus groups

Each account shard uses a correct five-node Raft cluster. A client debits one, then crashes before crediting the other. Was Raft violated?

Hint

Locate the invariant outside either individual log.

Worked answer
ShardCommitted updateReplication status
AdaDebit 10Correctly replicated
BoNo creditCorrectly unchanged
The transfer invariant fails above the per-shard replication layer.

No. Each shard may have followed its own consensus protocol perfectly. The client’s two-call workflow lacked a cross-shard atomic-commit or suitable business-recovery protocol. Replicating each piece does not atomically join the pieces.

Sources and further reading

The explanations and worked answers above stand alone. These references provide the original algorithms, assumptions, and deeper proofs; they are not required downloads.

Lesson browserDistributed consensus, replication, and fault tolerance lessonsPrevious: Recovery, snapshots, and membership changesNext: Leaderless replication and conflict-free data