CSE Roadmap

Common tier · about 4 hours · 6 parts

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.