10.9 Self-test

State the two philosophies for handling replica inconsistency and one situation where each is the only viable choice.

Define linearizability in one sentence. Why is it called a recency guarantee?

In the sports example, why does the violation depend on Aaliyah speaking? What is that channel called in general?

Given a write concurrent with three reads, which reads must return the old value, which must return the new, and which may return either?

State the extra constraint beyond "concurrent reads may return either." What would go wrong without it?

Distinguish linearizability from serializability on three axes. What is the combination called?

Give three categories of situation that genuinely require linearizability, and one type of constraint that does not.

Draw the video-transcoder race. Why does linearizable storage fix it, and what is the alternative if you control the queue?

For each replication method, say whether it can be linearizable and what breaks it.

Reproduce the quorum counterexample. What two changes would make Dynamo-style quorums linearizable, and what can never be made linearizable that way?

State the CAP trade-off properly. Why is "pick two of three" misleading?

Give three specific criticisms the book makes of CAP as a design tool.

Why is RAM on a multi-core CPU not linearizable? What does that tell you about why systems drop linearizability?

State the Attiya–Welch result and its practical consequence.

Give four distributed ID schemes and say precisely what ordering property each loses.

State the three requirements of a logical clock. Which one do sharded/UUID/timestamp schemes fail?

Give the two Lamport clock update rules and the comparison rule. Trace the chat example.

Give two limitations of Lamport clocks, and explain how HLCs fix each.

Why can't you tell from two Lamport timestamps whether the events were concurrent? What data structure can, and what does it cost?

Walk through the privacy-leak example. Which exact property of linearizability is violated, and why can't an HLC provide it?

Describe the batched timestamp oracle. What does batching sacrifice, and what does it preserve?

Why can't you shard a linearizable ID generator?

Why is a linearizable ID generator still insufficient for fault-tolerant locking?

What does the FLP result actually prove? Name the two ways real systems escape it.

State the four properties of single-value consensus. Which is the liveness property, and what is the minimum-node requirement it imposes?

Show both directions of the CAS ⟺ consensus equivalence.

State the five properties of a shared log. Sketch both directions of shared-log ⟺ consensus.

Why does fetch-and-add fail to solve consensus for three nodes but succeed for two? What is the term for this?

What is the one crucial difference between consensus and atomic commitment?

List six things you can build on top of a shared log.

How do consensus algorithms escape "you need a leader to elect a leader"? Name the epoch number in three algorithms.

Explain the quorum-overlap requirement between the two voting rounds. What does it prevent?

Give two ways consensus voting differs from 2PC.

What is unclean leader election, what does it buy, and what does it cost?

Why must linearizable reads also go through a quorum?

List five costs of consensus. Which one means you cannot scale throughput by adding nodes?

Which coordination-service features require consensus and which don't? Why is it still convenient to get the latter from the same service?

What is the architectural argument for a fixed 3–5 node coordination service in a system with thousands of shards?

Why is using consensus for service discovery usually overkill? What are ZooKeeper observers for?