for eleader, efollower in zip(leader, follower):
def log_matching_repair(leader, follower):
"""Return (truncate_from, entries_to_append) per Raft figure 7."""
# Longest common prefix: compare entries index-by-index (term AND index),
# stop at the first position where they diverge.
lcp = 0
for e_leader, e_follower in zip(leader, follower):
if e_leader == e_follower:
lcp += 1
else:
break
entries_to_append = leader[lcp:]
# If the follower still has entries at/after the LCP, it must delete them
# starting at that first index. If the follower is already a prefix of the
# leader (lcp == len(follower)), there is nothing to delete.
if lcp < len(follower):
truncate_from = follower[lcp][0] # stored log index of first bad entry
else:
truncate_from = None
return truncate_from, entries_to_append
Key decisions
(index, term) tuples. Raft logs at aligned positions share the same index, so tuple comparison reduces to "terms match index-by-index" while also guarding against misaligned/odd stored indices. zip stops at the shorter log, which is exactly the "leader shorter than follower" case.truncate_from is the stored log index of the first entry after the LCP (follower[lcp][0]), not a position — this handles both 0-indexed and 1-indexed logs and non-consecutive indices.None iff the follower is a prefix of the leader (lcp >= len(follower)), including empty-follower and identical-log cases: nothing to delete, only append leader[lcp:].Example: L=[(0,1),(1,2),(2,5)], F=[(0,1),(1,2),(2,3),(3,4)] → LCP=2 → returns (2, [(2,5)]); the follower keeps (0,1),(1,2) and ends with [(0,1),(1,2),(2,5)].
Verified with `test_raft_log_repair.py` (12 hand-written table cases × 3 checks + 2000 randomized fuzz trials = **2036 checks, all passing**). Table cases covering every stated edge case: - **Empty logs:** both empty → `(None, [])`; follower empty → `(None, L)`; leader empty → `(0, [])` (follower wiped). - **Follower prefix of leader:** `(None, [(2,3)])` — nothing deleted, rest appended. - **Leader shorter, full matching prefix:** `L=[(0,1),(1,2)]`, `F=[(0,1),(1,2),(2,3)]` → `(2, [])` — follower truncates its tail. - **Term divergence at index 0:** `(0, L)` — follower deletes from the very first entry. - **Divergence mid-log / conflicting tails / divergence after one match:** truncate at the first divergent index, append leader's suffix. - **1-indexed and non-consecutive indices:** `truncate_from` is the stored index (`3`, not a 0-based position). Each case was verified three ways: 1. **Exact return values** match expectations. 2. **Convergence:** simulating the follower side (`delete e where e[0] >= truncate_from`, then append) always reproduces the leader log exactly. 3. **Preservation:** the entries kept before `truncate_from` always equal the leader's prefix — nothing before the divergence point is ever deleted. Fuzz: 2000 trials constructing logs with a known random shared prefix (0- and 1-indexed, empty/shorter/longer suffixes, forced term divergence at the first conflicting index) — all converged and preserved the prefix.
{"model": "deepseek-v4-flash", "problem_class": "raft-log-repair-divergent-peers", "result": "passed", "tests": 2036}