Log Consistency

Raft's Log Matching Property: if two logs contain an entry with the same index and the same term, then (a) it is the same command, and (b) the two logs are identical in all preceding entries. Half (a) holds because a leader creates at most one entry per index in its term and never rewrites its own log. Half (b) is enforced one RPC at a time by the consistency check.

The consistency check

Every AppendEntries carries prev_log_index and prev_log_term — the coordinates of the entry immediately before the ones being sent. The follower accepts only if its own log has an entry at prev_log_index with exactly prev_log_term; otherwise it rejects, and the leader decrements that follower's next_index and retries one slot earlier. Induction: if the previous entry matches, everything before it already matched, so each accepted append extends the property.

Walk it — a leader vs. a follower that took entries from a rogue leader that died in term 4:

index:      1    2    3    4    5    6
leader:    t1   t1   t2   t2   t3   t3
follower:  t1   t1   t2   t4

next_index=7 -> prev=(6,t3): follower has no index 6       -> reject
next_index=6 -> prev=(5,t3): no index 5                    -> reject
next_index=5 -> prev=(4,t2): follower's idx 4 is t4 != t2  -> reject   <- the subtle probe
next_index=4 -> prev=(3,t2): follower's idx 3 is t2        -> ACCEPT
leader sends entries from idx 4: [t2, t3, t3]
follower deletes its conflicting t4 tail, appends -> t1 t1 t2 t2 t3 t3

The probe at prev=(4,t2) is where hand-rolled implementations go wrong: the check runs against the follower's entry at index 4 (term 4), not the leader's (term 2). An entry merely existing at the index is not enough — the terms must match.

Truncate only on conflict

The paper's receiver rule is precise: if an existing entry conflicts with a new one (same index, different term), delete it and everything after it; then append whatever entries are not already present. The trap is truncating unconditionally. RPCs arrive out of order, and an old, short AppendEntries showing up late would chop off entries you already acknowledged — entries the leader may already have counted toward a commit. That is committed-data loss caused by your own append handler. If the incoming entries match what you have, leave your tail alone.

Why overwriting a follower's tail is safe

It feels violent — the follower loses entries it durably stored. But any entry that was ever committed is on a majority and, by the election restriction, present in the current leader's log. So a suffix that conflicts with the leader's log was never committed: no client ever got an ack for it. Discarding it is not just safe; it is the point. One truth: the leader's log.

Backing up faster

One-slot-at-a-time convergence costs O(gap) round trips — painful after a long partition. The standard optimization: a rejecting follower returns the conflicting term and the first index it stores for that term, letting the leader skip a whole term per round trip instead of one entry.

Your exercise

Implement RECONCILE: afterwards the follower's log must equal the leader's byte for byte. The grader-caught mistake is treating a longer follower as "more up to date": with LEADER_LOG 1,1 and FOLLOWER_LOG 1,1,2,3, the output is 1,1 — the extra tail is uncommitted leftovers from a dead leader and must be truncated. Watch the empty forms too: reconciling any follower against LEADER_LOG (empty) prints (empty).