Implementing a Simplified Raft Consensus Algorithm

Distributed systems often require multiple nodes to agree on a state or a sequence of operations. Consensus algorithms are fundamental to achieving this agreement, ensuring fault tolerance and consistency even in the face of network issues or node failures. This challenge involves implementing a simplified version of the Raft consensus algorithm, a widely adopted protocol for distributed coordination.

Problem Description

Your task is to create a Python implementation of a simplified Raft consensus algorithm. The goal is to enable a cluster of nodes to elect a leader and replicate a log of operations to all followers. For this simplified challenge, we will focus on the leader election and basic log replication aspects.

Key Requirements:

1. Node States: Implement three distinct node states: Follower, Candidate, and Leader.
2. Leader Election:
   • Followers will time out and become Candidates.
   • Candidates will request votes from other nodes.
   • A Candidate becomes a Leader if it receives votes from a majority of the nodes.
   • If a Leader is not elected within a certain time, a new election should be triggered.
3. Log Replication (Simplified):
   • Once a Leader is elected, it can propose new log entries (commands).
   • The Leader will attempt to replicate these entries to its followers.
   • For this challenge, we will assume a deterministic scenario where replication is successful if the follower is available. We won't implement complex rollback or commit mechanisms for simplicity.
4. Timers: Implement distinct timeouts for follower heartbeats/election and for candidate election.
5. Message Passing: Simulate message passing between nodes. You can represent this with a central message queue or by directly calling methods on other nodes (for simulation purposes).

Expected Behavior:

• Initially, all nodes are Followers.
• A leader will eventually be elected.
• Once a leader exists, it should periodically send heartbeat messages to followers.
• If the leader fails, a new election should commence, and a new leader should be elected.
• The leader should be able to propose simple log entries, and these should be acknowledged by followers (in this simplified model).

Edge Cases:

• Network Partitions (Simulated): Consider scenarios where some nodes cannot communicate.
• Node Failures (Simulated): Simulate a node crashing and recovering.
• Split Votes: Scenarios where no candidate receives a majority, leading to a new election.

Examples

Example 1: Basic Leader Election

# Assume 3 nodes (node_a, node_b, node_c) all start as Followers.
# node_a's election timer expires first.
# node_a becomes Candidate, requests votes from node_b and node_c.
# node_b and node_c grant votes to node_a.
# node_a receives votes from a majority (2 out of 3) and becomes Leader.

# Initial state:
# node_a: Follower, term=0
# node_b: Follower, term=0
# node_c: Follower, term=0

# After node_a times out:
# node_a: Candidate, term=1, voted_for=node_a
# node_b: Follower, term=0
# node_c: Follower, term=0

# After vote requests and responses:
# node_a: Leader, term=1, log=[...]
# node_b: Follower, term=1
# node_c: Follower, term=1

Explanation: Node A, due to its election timer expiring, initiates an election. It wins the election by securing a majority of votes, becoming the leader.

Example 2: Leader Failure and Re-election

# Assume node_a is the Leader, term=5.
# node_a crashes (simulated by stopping its execution).
# node_b and node_c are Followers.
# node_b's election timer expires.
# node_b becomes Candidate, term=6, requests votes.
# node_c grants vote to node_b.
# node_b receives a majority and becomes Leader.

# State before failure:
# node_a: Leader, term=5
# node_b: Follower, term=5
# node_c: Follower, term=5

# node_a fails. node_b and node_c stop receiving heartbeats.

# After node_b times out:
# node_a: Failed
# node_b: Candidate, term=6, voted_for=node_b
# node_c: Follower, term=5

# After vote requests and responses:
# node_a: Failed
# node_b: Leader, term=6, log=[...]
# node_c: Follower, term=6

Explanation: When the leader fails, the remaining followers eventually time out and initiate a new election, resulting in a new leader being elected.

Example 3: Log Replication

# Assume node_a is Leader, term=7.
# node_a receives a command "set_value(10)".
# node_a appends "set_value(10)" to its log.
# node_a sends AppendEntries RPC to node_b and node_c.
# node_b and node_c append "set_value(10)" to their logs and acknowledge.

# State:
# node_a: Leader, term=7, log=["set_value(10)"]
# node_b: Follower, term=7, log=["set_value(10)"]
# node_c: Follower, term=7, log=["set_value(10)"]

Explanation: The leader proposes a new entry to its log and then replicates this entry to its followers. Successful replication leads to all nodes having the same log entry.

Constraints

• Number of Nodes: The cluster size will be between 3 and 5 nodes.
• Message Delay: Simulate message delays by introducing random delays for RPC calls.
• Timeouts: Election timeouts should be in the range of 150ms to 300ms. Heartbeat intervals should be less than the election timeout (e.g., 50ms).
• Node Availability: Nodes can be simulated to become unavailable and then available again.
• Data Structure: Log entries can be represented as simple strings or tuples.

Notes

• This challenge focuses on the core logic of Raft leader election and basic replication. You do not need to implement persistent storage for the log or state, network serialization, or complex commit logic.
• Consider using classes to represent your Node and its states.
• A simulation environment will be needed to manage the passage of time and the dispatching of messages between nodes. You might use a threading model or a simple event loop.
• Think about how to represent RPC calls (e.g., request_vote, append_entries) and how nodes will respond to them.
• Carefully manage the term number. Terms are monotonically increasing and are crucial for preventing outdated messages from being processed.
• When a node receives an RPC, it should compare the incoming term with its current term. If the incoming term is greater, it should step down to Follower and update its term. If the incoming term is less, it should reject the RPC.