db-19 step 02 — Discovery, sync, and atomic broadcast

Goal

Layer the steady-state ZAB protocol on top of the elected leader from step 01. The leader must bring every follower's history up to its own before accepting new proposals; once synced, the leader assigns a monotone zxid to each payload and commits it on majority ack. The dump bytes must match across Rust, Go, and C++.

Tasks

  1. Discovery (NewEpoch / AckEpoch). The fresh leader picks new_epoch = max(self.accepted_epoch, max-peer-accepted) + 1 and broadcasts NewEpoch { new_epoch }. Each follower:

    • Asserts new_epoch > accepted_epoch (refuse stale leaders).
    • Sets accepted_epoch = new_epoch.
    • Replies AckEpoch { current_epoch, last_zxid } — the follower's own committed epoch + tail of its history.

    The leader waits for a quorum of AckEpoch (counting itself). At quorum, it knows the highest zxid that any majority node has committed; that becomes the new initial history.

  2. Sync (NewLeader / AckLeader). Leader broadcasts NewLeader { new_epoch, history } where history is the leader's own log (which must include everything any quorum member has acked, by the contract of step 1). Each follower:

    • Asserts new_epoch > current_epoch (refuse historical leaders).
    • Replaces history with the leader's payload.
    • Sets current_epoch = new_epoch.
    • Replies AckLeader { new_epoch }.

    On quorum of AckLeader, the leader broadcasts Commit for every zxid in the synced history that has not yet been committed. The cluster is now in steady state.

  3. Broadcast (Propose / Ack / Commit). Each step tick, if there are queued proposals and we are the leader:

    • Assign zxid = ZxId { epoch: current_epoch, counter: ++last_counter }.
    • Append Txn { zxid, payload } to local history.
    • Broadcast Propose { txn } to all followers.

    Each follower asserts txn.zxid.epoch == current_epoch and txn.zxid > history.last().zxid, then appends and replies Ack { zxid }. The leader tracks acks per zxid in a BTreeMap<ZxId, BTreeSet<u32>>. On quorum (counting itself), it broadcasts Commit { zxid } and advances last_committed.

  4. Apply on commit. Followers receiving Commit { zxid } advance last_committed = max(last_committed, zxid) and (in a real system) apply the txn to the state machine. The lab leaves the state machine implicit — last_committed and history are the only observable surface.

  5. Canonical dump. dump_cluster(nodes) = magic("DSEZAB01") || u32 node_count || dump_node(0) || dump_node(1) || ... where dump_node = id u32 || role u8 || current_epoch u32 || accepted_epoch u32 || last_zxid (epoch,counter) || last_committed (epoch,counter) || history_len u32 || [zxid, payload_len u32, payload bytes] * history_len. All integers little-endian. hash = lowercase hex sha256 of the full byte string, no trailing newline.

Acceptance

Inline unit tests in each language:

  • discovery_bumps_accepted_epoch — leader elected at accepted_epoch=0 broadcasts NewEpoch{1}; followers reach accepted_epoch=1.
  • sync_replaces_follower_history_with_leader_history — follower with stale history receives NewLeader { history: leader_log } and ends with history == leader_log.
  • propose_commits_on_quorum_ack — leader in 3-node cluster proposes one txn; commits after 1 follower ack (leader + 1 = 2 = quorum). The third follower's late ack does not double-commit.
  • propose_does_not_commit_without_quorum — leader in 5-node cluster proposes, 1 follower acks; last_committed stays at ZxId::ZERO.
  • zxid_counter_is_monotone_per_epoch — three proposals get counter 1, 2, 3; if the leader's epoch bumps (next election), counter resets to 1 under the new epoch.
  • canonical_dump_is_byte_stable — same input scenario → same dump → same sha256 across two calls in the same process.

All six green in Rust, Go, and C++.