Part 6 of 6 · 3 min read
Exercises
Easy
Easy 1: Four properties (20 minutes)
Match each statement to a property: "no node changes its answer"; "the answer was one of the proposals"; "all live nodes finish"; "nodes never disagree".
Done when: four matches.
Hint
Safety properties are about nothing bad; termination is about progress.
Easy 2: Cluster sizes (20 minutes)
Give the majority and the tolerated failures for 3, 4, 5, 6 and 9 nodes.
Done when: a five-row table and one sentence on even numbers.
Hint
Majority is half the nodes plus one, rounded down.
Easy 3: What needs consensus (20 minutes)
Say whether each needs consensus: electing a leader; looking up a service address with stale results allowed; a unique user name; a page view counter.
Done when: four answers.
Hint
Stale answers are acceptable only for the second and fourth.
Medium
Medium 1: Commit trace (30 minutes)
Seven nodes. The leader appends entry 12 and sends it. Nodes 2, 3 and 4 reply yes, nodes 5 and 6 are slow, node 7 is down. When is entry 12 committed? How many failures could the cluster still survive?
Done when: a commit point and a failure count.
Hint
Count the leader as one of the nodes with the entry.
Medium 2: Who may win (30 minutes)
Candidate logs end at: A (index 8, term 4), B (index 9, term 3), C (index 9, term 4). Say which is the most up to date, and who may vote for whom.
Done when: a ranking and three vote rules applied.
Hint
Later term wins, then longer log.
Medium 3: Overlap proof (30 minutes)
Show that any two majorities of 5 nodes share a node, with a counting argument. Then show what goes wrong with a two-node "majority" of 5 and a three-node one of 6.
Done when: a short argument and two counter-examples.
Hint
Two sets of more than half must share a member.
Hard
Hard 1: Replay a failover (45 minutes)
Five nodes. Leader L has entries 1 to 6; entry 6 reached only L and F1. L crashes before committing 6. F2 (entries 1 to 5) becomes a candidate. Who can vote for it? Does it win? What happens to entry 6? Then repeat with entry 6 on L, F1 and F2.
Done when: two scenarios with outcomes and an explanation of why committed data is safe.
Hint
A candidate wins only if its log is at least as new as the log of every voter in its majority.
Hard 2: Use a coordination service (45 minutes)
Design a scheduler that runs a daily report on exactly one of 6 machines. Use a lock with a lease and a fencing token. Describe the keys, the session timeout, what happens during a 30-second pause of the holder, and what the report writer checks.
Done when: a design with keys, timings and a pause story.
Hint
The report writer must reject a token lower than the highest it has seen.
Hard 3: Cost and placement (50 minutes)
You must run a 5-node consensus group across 3 data centres. Place the nodes, say how many failures of nodes or of a whole data centre are tolerated, and estimate commit latency if the data centres are 10, 40 and 80 ms apart.
Done when: a placement, a failure table and a latency estimate with reasoning.
Hint
A majority of 5 is 3, so the commit waits for the second-nearest follower.