CHAPTER 7

Distributed Systems Theory

CAP, consistency, consensus, time and distributed transactions.

Source: Chapter 7 PDF, pp. 1–9

Learning objective

Understand why distributed systems fail in partial ways, reason about consistency and availability, and choose suitable mechanisms for coordination, transactions and safe retries.

Core PDF content

PDF page 11. Why are distributed systems difficult? p. 1

Imagine booking the last available flight seat. Two customers click Book at almost the same time, and separate servers receive the requests. The system must prevent both bookings from succeeding.

Figure 1: Two servers can receive competing requests; shared coordination must enforce the one-seat rule. — Figure 1. Two servers can receive competing requests; shared coordination must enforce the one-seat rule. · PDF p. 1

A distributed system is a collection of computers that communicate and cooperate to provide a service. Examples include payment platforms, messaging systems, cloud services and global databases.

Challenge	Why it matters
Partial failure	One server can fail while the rest continue running.
Unreliable network	Messages can be delayed, lost, duplicated or reordered.
Uncertain outcome	After a timeout, a request may have failed, succeeded or still be running.
Different clocks	Machine timestamps do not always establish the true order of events.

PDF page 22. CAP theorem: what happens when nodes cannot communicate? p. 2

Suppose a database stores two replicas. Normally they exchange updates, but a network failure separates them. Each server may still be running, yet they cannot reliably coordinate.

Figure 2: During a network partition, a system must decide whether to refuse or delay some operations or continue answering with possibly stale data. — Figure 2. During a network partition, a system must decide whether to refuse or delay some operations or continue answering with possibly stale data. · PDF p. 2

Property	Plain meaning
Consistency (C)	Successful reads observe the latest completed write according to a strong guarantee such as linearizability.
Availability (A)	Every request to a non-failing node receives a response, even if the response may be stale.
Partition tolerance (P)	The system is designed to operate despite network communication failures.

Two priorities during a partition

Choice	Behavior	Example fit
CP	Reject or delay requests when the system cannot ensure consistency.	Inventory, reservations, coordination.
AP	Continue answering, accepting that data may temporarily differ.	Some feeds, catalog views or low-risk updates.

CAP is about trade-offs during a partition. Partition tolerance is not optional in a distributed system exposed to real networks. A design decides how to behave when communication fails. PACELC adds the normal-operation trade-off: if there is a partition, choose between availability and consistency; else, choose between latency and consistency. Waiting for remote coordination can strengthen guarantees but increase response time.

PDF page 33. Consistency models and event ordering p. 3

When data is replicated, different users may observe updates at different times. A consistency model defines the guarantees about what they can observe.

Model	Guarantee	Example / consideration
Linearizable	Operations appear to take effect in real-time order; later reads see the latest completed write.	Strong coordination; may cost latency.
Sequential	Everyone sees operations in the same order, not necessarily real-time order.	Useful for ordered updates.
Causal	If event A caused B, everyone sees A before B.	A reply should follow its message.
Session guarantees	Rules such as read-your-writes or monotonic reads apply within a client session.	Can use routing or version tokens.
Eventual	If updates stop and repair succeeds, replicas converge.	May temporarily show stale data.

Example: read-your-writes

Figure 3: A write succeeds at the primary, but an immediate read from a lagging replica may return old data. — Figure 3. A write succeeds at the primary, but an immediate read from a lagging replica may return old data. · PDF p. 3

A common mitigation is to route recent reads to the primary, or to a replica known to have caught up. Other anomalies include seeing newer data and then older data, or seeing a reply before the message it answers. Time and event ordering

Figure 4: Clock skew and delayed messages make wall-clock timestamps an imperfect way to establish event order. — Figure 4. Clock skew and delayed messages make wall-clock timestamps an imperfect way to establish event order. · PDF p. 3

Technique	What it provides
Lamport clock	Logical counter that respects happened-before order but cannot identify all concurrent events.
Vector clock	Tracks counters by node to detect causally ordered or concurrent versions.
Hybrid logical clock	Combines physical time and a logical counter for useful monotonic timestamps.
TrueTime	Google Spanner uses bounded clock-uncertainty intervals to coordinate timestamps.

CRDTs are data structures with merge rules that allow supported updates to converge without immediate coordination. They can suit counters, sets and collaborative data, but are not a universal solution for conflicts such as allocating the last seat.

PDF page 44. Quorums: how many replicas must respond? p. 4

A quorum is the number of replicas that must participate in an operation. With N replicas, a write may wait for W acknowledgements, while a read contacts R replicas. A common overlap condition is W + R > N.

Figure 5: With N=3, W=2 and R=2, the read set and acknowledged write set must overlap. Read rules and version handling still matter. — Figure 5. With N=3, W=2 and R=2, the read set and acknowledged write set must overlap. Read rules and version handling still matter. · PDF p. 4

Setting	Typical trade-off
W=N, R=1	Writes wait for all replicas; reads contact one.
W=1, R=N	Writes can be fast; reads contact all replicas.
W=2, R=2, N=3	Read and write quorums overlap, helping reads discover acknowledged updates.

5. Consensus: getting nodes to agree p. 4

Consensus helps nodes agree on a value or decision, such as who is leader or which log entry should be committed, despite certain failures. Raft and Paxos are examples of consensus algorithms.

Figure 6: Simplified Raft flow: elect a leader, replicate log entries, and commit according to the protocol rules. — Figure 6. Simplified Raft flow: elect a leader, replicate log entries, and commit according to the protocol rules. · PDF p. 4

In a five-node voting cluster, three votes form a majority. Under the standard crash-failure model, a five-node cluster can tolerate two unavailable nodes if the remaining nodes can communicate as required. Consensus is used for leader election, replicated logs, configuration and coordination. It costs communication and may add latency, so reserve it for decisions that require agreement.

PDF page 56. Failure detection and gossip p. 5

A missed heartbeat does not prove that a node is dead. The node might be slow, overloaded, or separated by a network problem. Failure detectors therefore make suspicions based on timeouts and observed behavior.

Figure 7: A missed reply raises suspicion; systems need policies for confirmation, recovery and safe routing. — Figure 7. A missed reply raises suspicion; systems need policies for confirmation, recovery and safe routing. · PDF p. 5

Mechanism	Purpose	Caution
Heartbeats / timeouts	Check whether peers are responding.	Slow nodes can be suspected incorrectly.
Adaptive failure detector	Expresses suspicion based on observed timing, e.g. phi-accrual.	Still estimates failure; it cannot prove it from delay alone.
Gossip	Nodes exchange membership and state with selected peers; information spreads through the cluster.	Updates can take time to propagate.
Merkle-tree anti-entropy	Replicas compare hashes and synchronize only differing ranges.	Repair uses resources and needs suitable scheduling.

Split brain and fencing Split brain occurs when competing nodes both behave as leader. Quorums, terms/epochs and fencing help prevent an old or isolated leader from making conflicting changes. A fencing token is a monotonically increasing number attached to a lock grant; a protected resource rejects operations carrying older tokens.

PDF page 67. Distributed transactions: coordinating multiple services p. 6

A single business action may involve several services. For example, a holiday booking may reserve a flight, reserve a hotel and charge a payment. If a later step fails, the system needs a defined recovery path. Two-phase commit (2PC)

Figure 8: The coordinator asks participants to prepare, then commits if all can proceed; otherwise it aborts. — Figure 8. The coordinator asks participants to prepare, then commits if all can proceed; otherwise it aborts. · PDF p. 6

2PC can provide atomic commit across transactional participants, but it may hold resources and block if the coordinator or required participants become unavailable at a critical moment. Saga: a sequence of local transactions

Figure 9: If payment fails after reservations, compensating transactions attempt to release the earlier reservations. — Figure 9. If payment fails after reservations, compensating transactions attempt to release the earlier reservations. · PDF p. 6

A compensation is a new business action, not an erasure of history. A refund, for example, does not remove the original charge from the audit trail. Sagas make long workflows more flexible, but intermediate states may be visible and compensation can fail.

Approach	Idea	Trade-off
2PC / XA	Coordinator asks participants to prepare, then commit or abort.	Atomic commit; can block and hold resources.
Consensus-backed transactions	Replicated transactional protocols coordinate changes across shards.	Strong guarantees with coordination and latency costs.
Saga	Local transactions with compensating actions.	Intermediate states visible; compensation must be designed.
TCC	Try to reserve, then confirm or cancel.	Each service must support the three operations.
Outbox	Record business change and event in one local transaction.	Reliable publishing; consumer still handles duplicates.

PDF page 78. Retries, idempotency and reliable events p. 7

A request may succeed but its response may be lost. A caller that cannot tell what happened may retry, so systems must account for duplicates.

Figure 10: The service stores the result against a unique idempotency key and returns that result on retries. — Figure 10. The service stores the result against a unique idempotency key and returns that result on retries. · PDF p. 7

Delivery model	Meaning	Risk / handling
At-most-once	An operation is attempted no more than once.	It may be lost if delivery fails.
At-least-once	Retry until acknowledgement or policy limit.	Duplicates may arrive.
Exactly-once effect	Repeated deliveries do not repeat the logical side effect within a defined scope.	Requires idempotent processing, deduplication and suitable transaction boundaries.

For payment or order creation, a client sends a unique idempotency key. The service records the key and result atomically with the operation where possible. A retry with the same key returns the stored result rather than charging or creating a duplicate. The outbox pattern

Figure 11: The business row and event row commit together; a relay publishes events and consumers handle duplicates safely. — Figure 11. The business row and event row commit together; a relay publishes events and consumers handle duplicates safely. · PDF p. 7

The outbox avoids the failure where a database commit succeeds but publishing the related event fails. A relay can retry publication, so consumers still need idempotent processing.

PDF page 89. Putting the concepts together p. 8

Consider a global airline booking platform. Each distributed-systems idea solves a different class of problem.

Challenge	Useful concept
Two customers book the last seat.	Transactions and appropriate consistency guarantees.
A database server fails.	Replication, failover and safe promotion.
Replicas cannot communicate.	CAP trade-offs during a partition.
Nodes must elect one leader.	Consensus and majority quorums.
A request times out after succeeding.	Idempotency and duplicate protection.
Flight, hotel and payment must coordinate.	A saga or suitable distributed transaction.
A database change must reach other services.	Outbox, event publishing and idempotent consumers.

Chapter recap p. 8

Distributed systems must handle partial failures, delayed messages and uncertain event ordering.
CAP describes the consistency-versus-availability trade-off during a network partition; PACELC adds latency-versus-consistency during normal operation.
Consistency models define what users can observe. Logical clocks and CRDTs address different ordering and merge problems.
Quorums and consensus coordinate replicas, but the exact guarantees depend on the protocol.
Heartbeats and gossip help detect failures; fencing helps prevent stale leaders from making conflicting changes.
2PC, sagas, TCC and outbox patterns address different cross-service coordination needs.
Idempotency makes retries safer when requests or messages may be duplicated.

PDF page 9Check your understanding p. 9

Choose the best answer for each question, then review the answer key.

1. What does a timeout tell you about an operation?

A. It definitely failed
B. It definitely succeeded
C. Its outcome may be unknown

2. During a network partition, what does CAP say about strong consistency and full availability?

A. Both can always be guaranteed
B. A system must trade one against the other for affected requests
C. Consistency is irrelevant

3. What is the main purpose of consensus?

A. Compress database files
B. Help nodes agree on a decision despite certain failures
C. Eliminate all network latency

4. Why is an idempotency key useful for a payment request?

A. It guarantees the network never fails
B. It helps retries return the original result without charging twice
C. It prevents every payment error

5. A hotel reservation succeeds, but payment later fails. Which pattern can coordinate local steps and compensations?

A. Saga
B. DNS caching
C. Consistent hashing

6. Why use the outbox pattern?

A. To avoid recording events
B. To save a business change and its event in one local transaction
C. To guarantee every consumer runs exactly once

Answer key and explanations

1. C. The request may have succeeded even if its response never arrived.

2. B. During a partition, strong consistency and full availability cannot both be guaranteed for every request.

3. B. Consensus supports coordinated decisions such as leader election and replicated-log commitment.

4. B. A stored key and result help the service recognize repeated logical requests.

5. A. A saga uses local transactions and compensating actions to handle multi-step business workflows.

6. B. The outbox avoids losing an event when the database commit succeeds; duplicate delivery still needs handling.

Review questions for this chapter have not been written and reviewed yet. The chapter text above is the full source content.

References

Chapter 7 PDF, pp. 1–9; figures 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.

Ch. 6 Ch. 8: Messaging, Streaming and Async Processing

Tip: use ← and → keys to move between chapters.