Step 02 — Quorum Replication

Goal: extend the cluster to 5 replicas and make the leader commit only when a majority acks.

What to read first

  • docs/execution.md Stages 2 and 3.
  • The propose loop in src/rust/src/lib.rs (the part that calls try_append and counts acks).

Concrete tasks

  1. Implement Cluster::partition(ids) and is_partitioned. Store partitioned ids in a sorted set so iteration order is stable.
  2. In propose, count acks only from non-partitioned, non-leader replicas (plus one for the leader if the leader itself is not partitioned). If acks < quorum, return false and leave the entry uncommitted.
  3. Write the three quorum tests:
    • 5/5 reachable → commit on all.
    • 3/5 reachable → commit on the reachable three.
    • 2/5 reachable → no commit anywhere.

Definition of done

#![allow(unused)]
fn main() {
let mut c = Cluster::new(5);
c.partition(&[2, 3, 4]);
assert!(!c.propose(Op::Put("k".into(), b"v".to_vec())));
assert_eq!(c.leader().last_idx(), 1);
assert_eq!(c.leader().commit_index, 0);
}

passes. The Go and C++ ports must match.

Common bugs at this stage

  • Counting partitioned followers' acks anyway (a follower in the partitions set must contribute zero acks).
  • Counting the leader twice (once for i == leader_idx, once for acks = 1).
  • Advancing commit_index on the leader but not on the followers.
  • Mutating state_machine before the commit check passes.