A client sends “transfer $100” and times out. The service cannot infer failure: the request may have reached a leader, committed on a quorum, committed locally but not replicated, or never left the client. Distribution adds uncertain communication to already difficult transaction boundaries. Start with the fact that must remain true and the failures the system promises to handle.
A consistency claim must name its observer and failure
| Product fact | Unsafe observation | Plausible contract | Availability consequence |
|---|---|---|---|
| transfer never spends money twice | client sees two accepted debits | one ordered, durable decision plus idempotency | may reject/wait during leader loss |
| product search catches up | new item missing briefly | asynchronous indexed projection | stale result is visible and repairable |
| tenant authorization revocation | revoked user still reads data | strongly ordered or bounded-stale authorization path | read may wait/fail during partition |
| analytics counter | dashboard lags by a minute | convergent aggregate with stated window | value may be temporarily approximate |
A network partition does not prove which side contains the newest value. A timeout is an ambiguous outcome, so a client needs an operation ID and a status lookup or idempotent retry rather than a second independent request.
Prediction — client action after timeout
A payment request with idempotency key K times out. Which reply is safer: “failed,” “succeeded,” or “unknown; check K”?
Worked solutionExpandCollapse
“Unknown; check K” is the honest reply until the durable system of record resolves it. Retrying with the same key can be safe if the server persists and deduplicates K; retrying with a new key can create a second charge. A false success misleads the client, while a false failure can trigger duplicate work.
Quorum arithmetic proves only intersection
For N replicas, a read quorum R and write quorum W intersect when Two write quorums intersect when These inequalities establish shared replica membership; they do not alone establish leader fencing, version ordering, durability of a particular implementation, or linearizability.
For N replicas, a read quorum R and write quorum W intersect when Two write quorums intersect when These inequalities establish shared replica membership; they do not alone establish leader fencing, version ordering, durability of a particular implementation, or linearizability.
Test a quorum contract against failures
Set the replica count, read quorum, write quorum, and unavailable replicas. The model exposes the basic intersection condition R + W > N and its availability cost.
R + W = 4 > N = 3
3 reachable, need 2
3 reachable, need 2
Model scope: replicas are non-Byzantine, quorums are chosen from one fixed membership, an acknowledged write reaches W replicas, and a read consults R replicas with version reconciliation. Intersection alone does not solve concurrent writes, leader fencing, stale membership, clock uncertainty, anti-entropy, or application-level conflict resolution.
N = 3, R = 2, W = 2. Every read quorum intersects every write quorum, and one replica may be unavailable while reads and writes remain possible.
Static state: a three-replica, R=2/W=2 configuration provides quorum intersection and tolerates one unavailable replica for both operations.
Use the explorer to choose N, R, W, and failed replicas. Predict whether a read can obtain enough responses and whether its selected set must share a replica with a completed write. The model illustrates set intersection; a real protocol also needs a rule for choosing the newest valid version and for rejecting stale leaders.
Worked example — choose R and W
With N = 3 and W = 2, choose the smallest R that intersects every write quorum. Then state one thing the result still does not prove.
HintExpandCollapse
Use R + W > N, then list a protocol property outside set arithmetic.
Worked solutionExpandCollapse
R = 2, because 2 + 2 > 3. A read of two replicas intersects a completed two-replica write, but it still needs version/term rules to distinguish a newest value from a stale or divergent response. It also says nothing about whether a client received an acknowledgement before the intended data-loss boundary.
Quorum intersection and freshness
For an N = 5 node replica cluster, an architect configures read quorum R = 2 and write quorum W = 3. Evaluate which statements regarding quorum intersection and consistency are correct:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Coordination has a blocking and repair cost
| Design | Success rule | Partition / participant failure | Repair obligation |
|---|---|---|---|
| single database transaction | one local commit | one local failure domain | normal recovery |
| two-phase commit | coordinator collects prepare votes then decides | prepared participants can block awaiting decision | durable decision log and recovery protocol |
| saga / outbox | local commits advance an explicit state machine | temporary partial business state is visible | compensations, retries, and reconciliation |
| asynchronous projection | source event commits first | read model can lag | replay, watermark, and idempotent consumer |
Two-phase commit is not “a transaction across anything”: participants must durably prepare, a coordinator records a decision, and failure can leave prepared participants unable to decide alone. A saga makes partial progress explicit. It is suitable only when domain-level compensation can restore an acceptable business state; reversing a shipment after delivery is not the same as undoing a row update.
Transfer — avoid a fake atomicity claim
A system writes a financial ledger in region X and sends a warehouse reservation request to region Y. Region Y is unreachable after the ledger commit. Choose a design and state what the customer can see.
Worked solutionExpandCollapse
Use a durable outbox/state machine: record a pending reservation with the ledger transaction, retry the Y request idempotently, and expose “payment authorized, fulfillment pending” until the reservation succeeds or a defined compensation/refund occurs. Claiming an atomic cross-region success after X commits is false without a coordinating protocol and its availability cost. The visible intermediate state is a product decision, not a technical accident.
Distributed commit needs a durable decision, not a wish
Two-phase commit (2PC) makes a set of participants agree on one outcome. In the prepare phase the coordinator asks each participant to durably record its vote and the resources it will need to commit. If every participant votes yes, the coordinator durably records commit and then tells them to commit; if any votes no, it records abort. A participant that has prepared must retain its locks and its ability to commit until it learns the decision.
| Failure | What remains true | What the system cannot do alone |
|---|---|---|
| participant crashes after voting yes | its prepared state is durable | decide whether the coordinator chose commit or abort |
| coordinator crashes after recording commit | the decision is durable | notify unreachable participants until it recovers |
| coordinator crashes before recording a decision | no decision exists | force prepared participants to commit |
| network partition isolates a prepared participant | it cannot safely release locks | make progress without the decision |
The blocking case is fundamental to 2PC: prepared participants may hold locks while they wait for the coordinator. Three-phase commit removes some blocking under stronger assumptions, but adds rounds and still assumes bounded or predictable failures. A saga avoids prepared locks by making intermediate state visible, at the cost of requiring domain compensation.
Consensus protocols such as Paxos and Raft replicate a log, not a collection of independent row copies. A write is committed when a leader has replicated it to a quorum and the entry is ordered in the log; a new leader must contain every committed entry. Leader terms or epochs fence stale leaders so an old leader cannot acknowledge a write after a new one has been elected.
Spanner adds a physical ordering assumption: TrueTime exposes a bounded uncertainty interval for the local clock. A transaction waits out that uncertainty before committing, so timestamps assigned to committed transactions respect real-time order across regions. The result is external consistency, stronger than snapshot isolation, paid for with commit-wait latency and dependable clock infrastructure. Naming the assumption is part of the contract; a system without bounded clock uncertainty cannot copy the proof.
Transfer — choose the commit boundary
A cross-region transfer must never be visible as two independent halves, and the service cannot tolerate blocking during a coordinator failure. Which property must it give up, and what should it tell the client while a decision is pending?
HintExpandCollapse
A non-blocking design cannot also promise a single instantaneous cross-region commit without a stronger coordination substrate.
Worked solutionExpandCollapse
It must give up either non-blocking atomic commit or the claim of an instantaneous single decision. A durable outbox plus idempotent steps can keep serving, but the client sees an intermediate state such as “authorized, pending settlement.” A consensus-backed ledger can provide an ordered decision, but it may wait for a quorum and must expose a truthful pending status on timeout. Claiming both non-blocking operation and atomic cross-region success without naming the coordination mechanism is false.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 5.1.1: Quorum Overlap Inequality Verification
Referring to Proposition 5.1.1
HintExpandCollapse
Check the condition R + W > N.
Worked solutionExpandCollapse
Here Because by the Pigeonhole Principle the intersection of any read quorum of 4 nodes and any write quorum of 4 nodes contains at least node. Thus, every read quorum is mathematically guaranteed to contact at least one node that participated in the most recent successful write.
Exercise 5.1.2: CAP Theorem Partition Tolerance and Availability Boundaries
Explain why a distributed data store experiencing a network partition between two data centers must choose between consistency (rejecting writes in the minority partition) and availability (accepting conflicting writes in both partitions).
HintExpandCollapse
Nodes in separated partitions cannot communicate state updates synchronously.
Worked solutionExpandCollapse
During a network partition, nodes in partition cannot communicate with nodes in partition If the system chooses Availability, it must allow both partitions to accept writes independently, resulting in divergent states and violating linearizable Consistency. If the system chooses Consistency, nodes in the partition unable to contact a majority must refuse writes, sacrificing Availability for clients connected to that partition.
Exercise 5.1.3: Two-Phase Commit Coordinator Failure Analysis
In a two-phase commit protocol across three database nodes, participant votes YES during the prepare phase. The coordinator crashes before logging or broadcasting the commit/abort decision. Explain why remains blocked holding locks and cannot unilaterally decide to abort or commit.
HintExpandCollapse
P1 does not know if other participants voted NO or if the coordinator already told another node to commit.
Worked solutionExpandCollapse
cannot unilaterally abort because the coordinator might have received YES from all nodes and committed the transaction before crashing (or communicated commit to cannot unilaterally commit because another participant might have voted NO, causing the coordinator to abort. Consequently, must remain in the PREPARED state holding locks until the coordinator recovers or an election-based cooperative termination protocol resolves the outcome.
Exercise 5.1.4: Asynchronous Saga and Outbox Pattern Design for Multi-Region Workflows
An e-commerce order workflow requires debiting a customer’s account in region us-east and reserving warehouse stock in region eu-central. Network latency and transient partitions make 2PC unacceptable. Design a resilient asynchronous saga using transactional outboxes and compensating actions to handle stock exhaustion.
HintExpandCollapse
Use local database transactions in each region with an explicit intermediate state machine.
Worked solutionExpandCollapse
- Region
us-east: In a single local transaction, recordorder(id, status='pending'), deduct balance, and write anoutboxeventOrderPlaced. Commit. - Message transport: An outbox worker reliably delivers
OrderPlacedto an idempotent queue consumed byeu-central. - Region
eu-central: Attempts stock reservation in a local transaction.- If stock is available: Mark reserved and emit
StockReserved. - If stock is exhausted: Emit
StockFailed.
- If stock is available: Mark reserved and emit
- Compensation: Upon consuming
StockFailed,us-eastexecutes a compensating transaction that refunds the customer’s balance and transitions the order state tocancelled. Intermediate states (pending) are visible to users.
References & Further Reading
- Gray, J., & Lamport, L. (2006). Consensus on Transaction Commit. ACM TODS, 31(1), 133–160. (Two-phase commit, its blocking cases, and consensus-based commit.)
- Corbett, J. C., et al. (2012). Spanner: Google’s Globally-Distributed Database. OSDI ‘12. (TrueTime, commit-wait, and external consistency.)
- In Search of an Understandable Consensus Algorithm (Raft)
- CMU 15-445/645 Database Systems
- PostgreSQL: Synchronous Replication