Ensure Log Matching Property - The Consensus

                      TASK
                    

Implementation

Implement the Log Matching safety property:

On the follower side:

Receive AppendEntries with prevLogIndex, prevLogTerm
If entry at prevLogIndex has different term, reject
If entries conflict with existing, delete from conflict point
Append new entries
Update commitIndex if leader's is higher

This ensures all committed entries are identical across nodes.

Sample Test Cases

Accept matching entriesTimeout: 5000ms

Input

{"src":"c0","dest":"n2","body":{"type":"init","msg_id":1,"node_id":"n2","node_ids":["n1","n2","n3"]}}
{"src":"n1","dest":"n2","body":{"type":"append_entries","msg_id":2,"term":1,"leader_id":"n1","prev_log_index":0,"prev_log_term":0,"entries":[{"term":1,"index":1,"command":{"op":"put","key":"x","value":1}}],"leader_commit":0}}

Expected Output

{"src":"n2","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}
{"src":"n2","dest":"n1","body":{"type":"append_entries_ok","in_reply_to":2,"msg_id":1,"success":true,"match_index":1}}

Hints

Hint 1▾

Check prevLogIndex and prevLogTerm match

Hint 2▾

If conflict, truncate and replace

Hint 3▾

Never overwrite committed entries

                      OVERVIEW
                    

Theoretical Hub

Log Matching Invariant

If two nodes have entries with the same index and term, their logs are identical up to that point. This is achieved by rejecting AppendEntries when prev doesn't match, then backtracking until match is found.

Conflict Resolution

When logs diverge (after leader changes), the new leader's log wins. Followers truncate conflicting entries and accept the leader's. Committed entries are never truncated - that's the Election Restriction safety.

Key Concepts

log matchingconsistency checkconflict resolution

main.py

python

#!/usr/bin/env python3
import sys
import json
class Follower:
    def __init__(self, log):
        self.log = log  # RaftLog instance
        self.commit_index = 0
    
    def handle_append_entries(self, ae):
        # ae = {term, prev_log_index, prev_log_term, entries, leader_commit}
        
        # TODO: Check prev matches
        # TODO: Handle conflicts
        # TODO: Append new entries
        # TODO: Update commit index
        pass
    
    def _check_prev(self, prev_index, prev_term):
        # TODO: Check if log has matching entry
        pass
    
    def _find_conflict(self, entries):
        # TODO: Find first conflicting index
        pass
    
    def _apply_leader_commit(self, leader_commit):
        # TODO: Update commitIndex, apply entries
        pass