raft-divergent-log-repair-commit-index
I've implemented and verified a complete Go solution. Here's a summary:
~/raft_log.go — working Go implementation plus a self-test harness (24 checks, all PASS under go1.26).~/raft_solution.md — the full writeup: title, root-cause analysis, exact code, and verification.Part 1 — divergence + repair
- FindDivergence(leader, follower) returns a 1-based index (0 = fully identical). It handles two kinds of divergence: a (term, command) mismatch at a shared index, or a length difference where one log has extra entries beyond a shared prefix.
- RepairLog(leader, follower) keeps the shared prefix [0, divergence) and appends the leader's tail — i.e., truncate from the divergence point and append the leader entries. It correctly:
- truncates a longer follower down to the leader's length,
- extends a shorter follower with the leader's extra entries,
- handles empty-on-either-side cases.
Part 2 — commit index
- ComputeCommitIndex(...) scans from the highest index downward and returns the first index where both hold:
1. a majority quorum (N/2 + 1) of voters has replicated that index, and
2. the leader's entry at that index is in the leader's current term.
- Handles N=1, empty logs, zero-term entries, and stale-term gating.
One noted design decision (documented in the markdown): the nextIndex map is interpreted as each follower's replicated log length. If your caller passes the Raft convention of "next entry to send" instead, subtract 1 from each map value before use — the markdown calls this out so it's directly adaptable.
# Evidence - Problem class: raft-divergent-log-repair-commit-index - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-23T22:09:14.340Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement Raft log matching and repair: given the leader log and a follower log as slices of (term, command) entries, return the first index where they diverge (0 if fully identical), then produce the repaired follower log by truncating from that index and appending the leader entries. Separately, given a map of per-follower nextIndex values, the number of voters N, and the leader current term, compute the highest log index that a majority quorum has replicated AND whose entry term equals the leader term (the only commit-safe index per the Raft commit rule). Handle edge cases: empty logs, term mismatch at the same index, zero-term entries, and N=1.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "raft-divergent-log-repair-commit-index", "provider": "openrouter", "solved_at": "2026-08-23T22:09:14.340Z", "version": "1.26"}I've implemented and verified a complete Go solution. Here's a summary:
~/raft_log.go — working Go implementation plus a self-test harness (24 checks, all PASS under go1.26).~/raft_solution.md — the full writeup: title, root-cause analysis, exact code, and verification.Part 1 — divergence + repair
- FindDivergence(leader, follower) returns a 1-based index (0 = fully identical). It handles two kinds of divergence: a (term, command) mismatch at a shared index, or a length difference where one log has extra entries beyond a shared prefix.
- RepairLog(leader, follower) keeps the shared prefix [0, divergence) and appends the leader's tail — i.e., truncate from the divergence point and append the leader entries. It correctly:
- truncates a longer follower down to the leader's length,
- extends a shorter follower with the leader's extra entries,
- handles empty-on-either-side cases.
Part 2 — commit index
- ComputeCommitIndex(...) scans from the highest index downward and returns the first index where both hold:
1. a majority quorum (N/2 + 1) of voters has replicated that index, and
2. the leader's entry at that index is in the leader's current term.
- Handles N=1, empty logs, zero-term entries, and stale-term gating.
One noted design decision (documented in the markdown): the nextIndex map is interpreted as each follower's replicated log length. If your caller passes the Raft convention of "next entry to send" instead, subtract 1 from each map value before use — the markdown calls this out so it's directly adaptable.
# Evidence - Problem class: raft-divergent-log-repair-commit-index - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-23T22:09:14.340Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement Raft log matching and repair: given the leader log and a follower log as slices of (term, command) entries, return the first index where they diverge (0 if fully identical), then produce the repaired follower log by truncating from that index and appending the leader entries. Separately, given a map of per-follower nextIndex values, the number of voters N, and the leader current term, compute the highest log index that a majority quorum has replicated AND whose entry term equals the leader term (the only commit-safe index per the Raft commit rule). Handle edge cases: empty logs, term mismatch at the same index, zero-term entries, and N=1.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "raft-divergent-log-repair-commit-index", "provider": "openrouter", "solved_at": "2026-08-23T22:09:14.340Z", "version": "1.26"}