Skip to main content

Consensus Reasoning Clinic

Retrieval Prompts​

  1. State the three safety properties of consensus (agreement, integrity, validity) and the one liveness property (termination).
  2. State the FLP impossibility result in one sentence and the partial-synchrony assumption that real systems use to escape it.
  3. Describe the two phases of basic Paxos from memory.
  4. Describe the three Raft roles and when a node transitions between them.
  5. State Raft's election restriction and why it is needed.
  6. State the log-matching property and why it lets AppendEntries back up one index at a time.

Compare and Distinguish​

Separate these:

  • consensus vs leader election (and why the latter is a special case)
  • consensus vs atomic commit
  • Multi-Paxos vs Raft
  • Paxos proposer vs Raft leader
  • "chosen" in Paxos vs "committed" in Raft
  • fencing token vs lock TTL

Common Mistake Check​

For each, identify the error:

  1. "Raft guarantees exactly-once client semantics."
  2. "A 4-node Raft cluster is fine - it can tolerate one failure."
  3. "If a Paxos proposer gets no reply, it should propose a new value with a lower proposal number."
  4. "Under Raft, if the leader crashes, any follower can become the new leader."
  5. "FLP says consensus is unsolvable, so Paxos and Raft are unsound."

Paxos Trace by Hand​

Three acceptors A, B, C. Walk through this sequence and write down the accepted (n, v) at each acceptor after each step:

  1. Proposer P1 runs Phase 1 with n=1 at A and B; both promise.
  2. P1 runs Phase 2 with (1, "X") at A and B; both accept.
  3. Proposer P2 runs Phase 1 with n=2 at B and C.
  4. What must B reply? What must C reply?
  5. Given the replies, what value must P2 propose in Phase 2?
  6. P2 runs Phase 2 at B and C. What is the final chosen value?

Write it out. Verify safety: no two quorums can chose different values.

Raft Trace by Hand​

5 nodes: N1 through N5. Term starts at 1; N1 is leader.

  1. N1 appends entries at indices 1, 2, 3 (all term 1) and replicates to N2, N3. Entries 1-3 are committed.
  2. Network partitions: {N1, N2} on side A, {N3, N4, N5} on side B.
  3. N1 appends entry 4 at term 1 (still leader in its partition), replicates to N2. N1 cannot get a majority, so entry 4 is not committed.
  4. On side B, N3's election timer fires. N3 becomes candidate at term 2. It gets votes from N4 and N5. (Check the election restriction: their logs end at index 3 term 1; N3's log ends at index 3 term 1. Legal.)
  5. N3 is leader at term 2. Client writes arrive. N3 appends entries 4 and 5 at term 2 and replicates to N4, N5. Entries 4-5 (at term 2) are committed.
  6. Partition heals. N1 and N2 are still running at term 1.

Answer:

  • What happens when N1 sends AppendEntries to N3?
  • What happens when N3 sends AppendEntries to N1?
  • What entry ends up at each node's index 4? What is its term?
  • What did we commit at term 2 that N1 had at term 1?
  • Is this safe? Cite the specific Raft invariant.

Split-Brain Reasoning​

A cluster has 5 Raft nodes. 3 of them are in zone A (including the leader), 2 in zone B. Zones partition.

  1. Can zone A still make progress? Why?
  2. Can zone B elect its own leader? Why or why not?
  3. After the partition heals, which writes survive and which are rolled back?
  4. How does a fencing token prevent split-brain writes during the transition?

Paxos vs Raft Decision​

You need to pick a consensus implementation for a new internal scheduler. Constraints:

  • 5 nodes, one region
  • Throughput needs are modest (hundreds of decisions per second)
  • The team has not done consensus before
  • The system must tolerate one datacenter-zone outage

Write one page: which would you pick (a Raft library, a Paxos-family library, or a full coordination service), and why. Include at least one argument against the other choice.

Evidence Check​

This practice page is complete only if you can:

  • Trace both a Paxos Phase 1/Phase 2 run and a Raft election + replication round by hand, end to end, including failure injection.
  • Argue why a given Raft log evolution is safe using specific invariant names.
  • Explain why a 4-node Raft cluster is strictly worse than a 3-node or 5-node cluster.
  • Reason about split-brain during and after a partition, including the role of the fencing token.