Log Replication

The leader turns client commands into an ordered, replicated log. Every entry is a triple — (index, term, command) — where the index is its position and the term stamps which leadership era appended it. That term stamp is what every later safety rule keys off.

The write path

1. client sends "set x=5" to the leader (followers redirect clients)
2. leader appends (idx=1, term=2, "set x=5") locally  — nothing acked yet
3. leader sends AppendEntries to every follower in parallel:
      (term, prev_log_index, prev_log_term, entries[], leader_commit)
4. each follower appends and acks
5. entry on a MAJORITY of nodes (leader included) -> committed:
      leader applies "x=5" to its state machine, replies OK to the client
6. later AppendEntries carry leader_commit; followers apply up to it

Two deliberate asymmetries to internalize:

Why a majority — not all, not fewer? Wait for all and one dead follower freezes every write: you built a system with worse availability than a single box. Wait for fewer than a majority and you lose acknowledged data: in a 5-node cluster, suppose the leader acks after one follower ack. Those two nodes burn down together; the surviving three form a majority, elect a leader that never saw your entry, and move on. The client holds an OK for a write no live node remembers. Majority is the unique threshold where every future election majority must overlap the replication set.

Why do followers apply later? The client needs durability against f failures, which commit provides; it does not need every replica to have applied. Followers learn the commit frontier from leader_commit on the next RPC and catch up. Commit and apply are separate cursors — commit_index vs last_applied — and conflating them is a classic bug.

Heartbeats are just empty AppendEntries — same RPC, zero entries, sent every ~50–100 ms so follower timers never fire while a leader lives. A follower rejects any AppendEntries whose term is below its own (stale leader) or whose prev_log_index/prev_log_term don't match its log (divergence — the next lesson is entirely about this).

Leader bookkeeping

Per follower, the leader tracks next_index (next entry to send; decremented on rejection) and match_index (highest entry known replicated there). Sort the match indexes and take the majority point: that is the newest index a majority holds — the commit candidate. (One extra restriction lands in the Figure-8 lesson: only entries from the leader's current term may commit by counting.)

The majority-arithmetic trap

Your exercise has 1 leader + n followers: the cluster is n+1 nodes and commit needs (n+1)//2 + 1 holders, the leader counting as one of them. With 6 followers (7 nodes) that is 4: the leader plus THREE acks. Off-by-one here silently "commits" entries that a perfectly legal election could erase.

Your exercise

Simulate replication and commit. The grader-caught mistake is exactly that arithmetic: after INIT 6, one CLIENT, and acks from followers 1 and 2, COMMIT_INDEX must print 0 — only the third ack flips it to 1. Also remember an ACK means the follower now holds the leader's entire log so far: with two pending entries, two acks commit both, so COMMIT_INDEX prints 2, not 1. And LOG 0 on an empty log prints (empty) — exactly.