โ˜… Final Challenge

โ€บ A Deterministic Cluster

100 pts

Time to assemble the machine. You get a three-node in-memory cluster where time is ticks and the network is a queue, and you implement the entire Raft node logic โ€” election, log replication, and commitment โ€” as two pure functions:

  • Tick(n *Node) []Message โ€” one clock tick (lesson 5).
  • Step(n *Node, m Message) []Message โ€” apply one incoming message, return the replies (lessons 1โ€“4).

The Cluster harness is already written for you โ€” read it, leave it alone. It ticks nodes in ID order, queues whatever they emit, and Deliver/DeliverAll pump the queue FIFO, dropping messages that cross a partition (Isolate/ Heal). Propose appends a client command to a node's log stamped with that node's current term. The tests stage everything deterministically: election timeouts are [4, 6, 8] ticks for nodes 0, 1, 2, heartbeats every 2 ticks โ€” so node 0 always wins the first election, and node 1 takes over when node 0 is isolated.

Implement to this spec (Figure 2, restated for our tick model):

Tick โ€” as in lesson 5, with one upgrade: a leader's broadcast is a full MsgAppendRequest per peer, in Peers order, carrying Entries = Log[NextIndex[peer]-1:] (copy the slice), PrevLogIndex = NextIndex[peer]-1 with the matching PrevLogTerm, and LeaderCommit = CommitIndex. When there is nothing new for a peer this is naturally an empty heartbeat.

Step โ€” for every message: if m.Term > n.CurrentTerm, adopt the term, become Follower, reset VotedFor to -1 and VotesGranted to 0, then keep processing. Then by type:

  • MsgVoteRequest: the lesson-2 receiver rules. Always reply with a MsgVoteReply carrying your CurrentTerm; on granting, also reset ElectionElapsed to 0.
  • MsgVoteReply: only candidates count them, only if Granted and m.Term == CurrentTerm. On reaching a majority of len(Peers)+1, become leader: for every peer set NextIndex[peer] = len(Log)+1 and MatchIndex[peer] = 0, reset HeartbeatElapsed to 0, and immediately return a first round of heartbeats (same form as a leader tick) to assert authority.
  • MsgAppendRequest: the lesson-3 receiver rules. Any valid request (term not stale) makes you a Follower and resets ElectionElapsed. Reply with a MsgAppendReply carrying your CurrentTerm, Success, and โ€” when successful โ€” MatchIndex = m.PrevLogIndex + len(m.Entries).
  • MsgAppendReply: leaders only, and only for m.Term == CurrentTerm. On Success: raise MatchIndex[m.From] and NextIndex[m.From] (to m.MatchIndex and m.MatchIndex+1; never lower them), then advance CommitIndex with the lesson-4 rule โ€” largest N > CommitIndex with Log[N-1].Term == CurrentTerm stored on a majority, counting yourself. On failure: decrement NextIndex[m.From] (not below 1); the retry rides the next heartbeat tick.

Every reply's From/To must be set (From = n.ID, To = m.From). If a message needs no reply, return nothing for it.

The tests walk the cluster through the full Raft story: nothing happens before the first timeout; node 0 is elected in term 1; a proposed command replicates and commits on a majority, with followers learning the commit index one heartbeat later; node 0 is partitioned away, node 1 wins term 2 with node 2's vote while the stale leader keeps ruling its network of one; and after the partition heals, the old leader sees term 2, steps down, and converges on the new leader's log.

Log in to submit a solution and earn points.