Search Knowledge

© 2026 LIBREUNI PROJECT

Database Systems/Data at scale and synthesis
Page 16 of 20

Distributed Data

Choose consistency and coordination contracts from a precise failure model instead of treating replication as a universal guarantee.

Lesson briefData at scale and synthesis · 7 h · 4 outcomes

Required knowledge

  • Transactions, isolation, logs, retries, and idempotent external effects
  • Basic probability and set intersection
  • Network partitions, crash failures, and the difference between latency and correctness

Learning outcomes

  • State the failure model and client-visible consistency requirement before choosing a distributed-data mechanism.
  • Derive when read and write quorums intersect and identify the assumptions the arithmetic does not supply.
  • Compare a single-writer transaction, distributed commit, and saga/compensation by atomicity, availability, and repair evidence.
  • Design a client response to timeout, stale read, and ambiguous commit without inventing a result.

Assessment target

Given a distributed order or authorization workflow under a partition, choose a consistency contract, trace the durable decision and client response, and defend the availability trade-off with a counterexample.

Scope boundary

  • Two-phase commit and consensus-backed replication are taught through their failure contracts and commit rules. Formal consensus proofs, Byzantine faults, geo-replication implementation, and CRDT design are deferred.
  • Vendor topology configuration is used only as an explicit example, not as a general distributed-systems model.

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 factUnsafe observationPlausible contractAvailability consequence
transfer never spends money twiceclient sees two accepted debitsone ordered, durable decision plus idempotencymay reject/wait during leader loss
product search catches upnew item missing brieflyasynchronous indexed projectionstale result is visible and repairable
tenant authorization revocationrevoked user still reads datastrongly ordered or bounded-stale authorization pathread may wait/fail during partition
analytics counterdashboard lags by a minuteconvergent aggregate with stated windowvalue 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 solutionExpand

“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

Proposition 5.1.1Read/write quorum intersection

For N replicas, a read quorum R and write quorum W intersect when R+W>NR + W > N Two write quorums intersect when 2W>N2W > N These inequalities establish shared replica membership; they do not alone establish leader fencing, version ordering, durability of a particular implementation, or linearizability.

Interactive exploration

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.

Read/write quorums intersect. Reads are available; writes are available.
Read quorum R = 2
Write quorum W = 2
Unavailable replicas = 0
Replica 1reachable
Replica 2reachable
Replica 3reachable
Intersection
R + W = 4 > N = 3
Read availability
3 reachable, need 2
Write availability
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.

Test a quorum contract against failures
Replica 1reachable
Replica 2reachable
Replica 3reachable

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.

Code
participant "client" as C
participant "leader" as L
database "replica A" as A
database "replica B" as B
database "replica C" as D
C -> L : write transfer K
L -> A : replicate entry 44
L -> B : replicate entry 44
L -> C : acknowledge after quorum
note right of C
The client contract depends on
what quorum acknowledgement means.
end note
clientleaderreplica Areplica Breplica Cclientclientleaderleaderreplica Areplica Areplica Breplica Breplica Creplica Cwrite transfer Kreplicate entry 44replicate entry 44acknowledge afterquorumThe client contract depends onwhat quorum acknowledgementmeans.

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.

HintExpand

Use R + W > N, then list a protocol property outside set arithmetic.

Worked solutionExpand

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

0 / 4 answered

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.

1
Monotonic read consistency is not guaranteed without client session stickiness or version tracking across queries.
2
Because R + W = 5 <= N, a read of 2 nodes can miss all 3 nodes written by the previous write, returning stale data.
3
Every read quorum intersects every write quorum in this configuration, guaranteeing strict linearizable read behavior.
4
During any network partition splitting 5 nodes into 2 and 3, both isolated partitions can continue accepting write quorums.

Coordination has a blocking and repair cost

DesignSuccess rulePartition / participant failureRepair obligation
single database transactionone local commitone local failure domainnormal recovery
two-phase commitcoordinator collects prepare votes then decidesprepared participants can block awaiting decisiondurable decision log and recovery protocol
saga / outboxlocal commits advance an explicit state machinetemporary partial business state is visiblecompensations, retries, and reconciliation
asynchronous projectionsource event commits firstread model can lagreplay, 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 solutionExpand

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.

FailureWhat remains trueWhat the system cannot do alone
participant crashes after voting yesits prepared state is durabledecide whether the coordinator chose commit or abort
coordinator crashes after recording committhe decision is durablenotify unreachable participants until it recovers
coordinator crashes before recording a decisionno decision existsforce prepared participants to commit
network partition isolates a prepared participantit cannot safely release locksmake 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?

HintExpand

A non-blocking design cannot also promise a single instantaneous cross-region commit without a stronger coordination substrate.

Worked solutionExpand

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.

Section Exercises

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

Verificationapplication

Referring to Proposition 5.1.1, evaluate a distributed cluster with N=7N = 7 nodes configured with write quorum W=4W = 4 and read quorum R=4R = 4 Verify whether every read is guaranteed to observe at least one node containing the latest committed write.

HintExpand

Check the condition R + W > N.

Worked solutionExpand

Here R+W=4+4=8R + W = 4 + 4 = 8 Because 8>78 > 7 R+W>NR + W > N by the Pigeonhole Principle the intersection of any read quorum of 4 nodes and any write quorum of 4 nodes contains at least 4+4−7=14 + 4 - 7 = 1 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

Descriptionrecall

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).

HintExpand

Nodes in separated partitions cannot communicate state updates synchronously.

Worked solutionExpand

During a network partition, nodes in partition AA cannot communicate with nodes in partition BB 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

Constructionapplication

In a two-phase commit protocol across three database nodes, participant P1P_1 votes YES during the prepare phase. The coordinator crashes before logging or broadcasting the commit/abort decision. Explain why P1P_1 remains blocked holding locks and cannot unilaterally decide to abort or commit.

HintExpand

P1 does not know if other participants voted NO or if the coordinator already told another node to commit.

Worked solutionExpand

P1P_1 cannot unilaterally abort because the coordinator might have received YES from all nodes and committed the transaction before crashing (or communicated commit to P2P_2 P1P_1 cannot unilaterally commit because another participant might have voted NO, causing the coordinator to abort. Consequently, P1P_1 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

Generalisationtransfer

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.

HintExpand

Use local database transactions in each region with an explicit intermediate state machine.

Worked solutionExpand
  1. Region us-east: In a single local transaction, record order(id, status='pending'), deduct balance, and write an outbox event OrderPlaced. Commit.
  2. Message transport: An outbox worker reliably delivers OrderPlaced to an idempotent queue consumed by eu-central.
  3. 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.
  4. Compensation: Upon consuming StockFailed, us-east executes a compensating transaction that refunds the customer’s balance and transitions the order state to cancelled. Intermediate states (pending) are visible to users.

References & Further Reading