Implement Multi-Paxos for an Infinite Log - The Consensus

Implementation

Extend single-decree Paxos to Multi-Paxos: an infinite log where each slot is a separate Paxos instance.

Key optimization: once leadership is established, skip Phase 1 for subsequent slots. Only run Phase 2 (Accept) directly.

Request:  {"type": "multi_paxos_propose", "msg_id": 1, "slot": 1, "value": "set x=1"}
Response: {"type": "multi_paxos_propose_ok", "in_reply_to": 1, "slot": 1, "phase1_skipped": false, "chosen": true, "value": "set x=1"}

Request:  {"type": "multi_paxos_propose", "msg_id": 2, "slot": 2, "value": "set y=2"}
Response: {"type": "multi_paxos_propose_ok", "in_reply_to": 2, "slot": 2, "phase1_skipped": true, "chosen": true, "value": "set y=2"}

Request:  {"type": "multi_paxos_log", "msg_id": 3}
Response: {"type": "multi_paxos_log_ok", "in_reply_to": 3, "log": [
    {"slot": 1, "value": "set x=1", "status": "chosen"},
    {"slot": 2, "value": "set y=2", "status": "chosen"}
]}

Sample Test Cases

First slot requires Phase 1Timeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"multi_paxos_propose","msg_id":2,"slot":1,"value":"cmd1"}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Subsequent slots skip Phase 1Timeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"multi_paxos_propose","msg_id":2,"slot":1,"value":"cmd1"}}
{"src":"c1","dest":"n1","body":{"type":"multi_paxos_propose","msg_id":3,"slot":2,"value":"cmd2"}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Hints

Hint 1▾

Multi-Paxos runs a separate Paxos instance for each log slot

Hint 2▾

Optimization: once a leader is stable, skip Phase 1 for subsequent slots

Hint 3▾

The leader only needs Phase 2 (Accept/Accepted) for new entries

Hint 4▾

If the leader changes, Phase 1 must be re-run for the next slot

Hint 5▾

This is essentially how Raft works but with Paxos terminology

Implementation

Sample Test Cases

Hints

Resources

Theoretical Hub

Key Concepts