Part 5 of 5 · 4 min read
Exercises
Easy
Easy 1: State the consensus problem (15 minutes)
State, in one sentence, what the consensus problem requires.
Done when: a set of nodes agreeing on one single value, with every node that decides reaching the same decision, is correctly described.
Hint
A set of nodes agreeing on one single value, with every node that decides reaching the same decision.
Easy 2: State two-phase commit's key weakness relative to consensus (15 minutes)
State why two-phase commit can block forever in a way a true consensus protocol avoids.
Done when: two-phase commit's reliance on a single coordinator, which can leave the system blocked if that coordinator fails permanently, is correctly identified.
Hint
It relies on a single coordinator, which can leave the system blocked forever if that coordinator fails permanently.
Easy 3: Define a majority quorum (15 minutes)
State what a majority quorum is in the context of a consensus protocol.
Done when: more than half of the nodes in a group is correctly described.
Hint
More than half of the nodes in a group.
Medium
Medium 1: Explain why majorities must overlap (25 minutes)
Explain why any two majorities drawn from the same group of nodes must share at least one common node.
Done when: the explanation correctly notes that since a majority is more than half of the group, two separate majorities cannot both avoid overlapping, because together they would need more nodes than actually exist in the group.
Hint
Since a majority is more than half of the group, two separate majorities together would need more nodes than exist in the group, so they must overlap.
Medium 2: Determine how many node failures a 7-node cluster tolerates (25 minutes)
A consensus protocol runs on 7 nodes. Determine the maximum number of node failures the cluster can tolerate while still being able to form a majority.
Done when: 3 is correctly identified, since 4 of the remaining nodes would still form a majority of 7, while losing 4 nodes would leave only 3, which is not a majority.
Hint
3 node failures, since the remaining 4 nodes still form a majority of 7, while losing a 4th would leave only 3, not a majority.
Medium 3: Identify a consensus problem in a described scenario (30 minutes)
A group of nodes must agree on which single node should act as leader for the next period, with agreement required even if several candidate nodes propose themselves simultaneously. Identify what kind of problem this is.
Done when: this is correctly identified as a consensus problem, since it requires the group to agree on a single value, here the identity of the leader, despite multiple competing proposals.
Hint
A consensus problem, since the group must agree on a single value, here the leader's identity, despite multiple competing proposals.
Hard
Hard 1: Explain why two-phase commit cannot simply replace its coordinator (30 minutes)
Explain why simply adding a backup coordinator to two-phase commit, promoted whenever the primary coordinator fails, does not by itself turn two-phase commit into a fault-tolerant consensus protocol.
Done when: the explanation correctly notes that without a majority-based mechanism to guarantee the backup coordinator has the same, correct view of whatever decision may already have been made or implied before the failure, the backup risks making a different decision than the original coordinator would have, which is exactly the disagreement a true consensus protocol is designed to prevent.
Hint
Without a majority-based mechanism ensuring the backup coordinator has the same correct view of any decision already made, it risks making a different decision, exactly the disagreement consensus is meant to prevent.
Hard 2: Explain why an even-sized cluster is a poor choice for consensus (35 minutes)
Explain why a consensus protocol's cluster size is typically chosen to be an odd number, such as 5 or 7, rather than an even number such as 4 or 6.
Done when: the explanation correctly notes that an odd-sized cluster gets the same fault-tolerance benefit as the next even size while needing one fewer node, since, for example, a cluster of 5 and a cluster of 6 both tolerate only 2 failures to keep a majority, so the 6th node adds cost without adding fault tolerance.
Hint
An odd-sized cluster gets the same fault tolerance as the next even size with one fewer node, since, for example, both 5 and 6 nodes only tolerate 2 failures while keeping a majority.
Hard 3: Connect the consensus problem to leader election in replication (40 minutes)
Replication, covered in an earlier level, relies on designating a leader. Explain how choosing a new leader after a leader fails is, at its core, an instance of the consensus problem.
Done when: the explanation correctly identifies that every node in the replicated system must agree on which single node is now the leader, with the same guarantee the consensus problem requires, that every node reaching a decision reaches the same decision, applying directly to this leader-election scenario.
Hint
Every node must agree on which single node is now the leader, with the same single-decision, same-outcome guarantee the consensus problem requires, making leader election a direct instance of consensus.