TASK
Implementation
Compare Raft and Multi-Paxos across multiple dimensions. Both solve the same problem (replicated log) but make different design tradeoffs.
Request: {"type": "compare_consensus", "msg_id": 1}
Response: {"type": "compare_consensus_ok", "in_reply_to": 1, "comparison": {
"raft": {"leader_change_cost": "O(uncommitted_entries)", "log_gaps": false, "understandability": "high", "production_users": ["etcd", "TiKV", "CockroachDB"]},
"multi_paxos": {"leader_change_cost": "O(1) per slot", "log_gaps": true, "understandability": "low", "production_users": ["Chubby", "Spanner", "Megastore"]}
}}
Request: {"type": "simulate_leader_change_cost", "msg_id": 2, "protocol": "raft", "uncommitted_entries": 50, "cluster_size": 5}
Response: {"type": "simulate_leader_change_cost_ok", "in_reply_to": 2, "messages_needed": 200, "rounds_needed": 50}
Request: {"type": "simulate_leader_change_cost", "msg_id": 3, "protocol": "multi_paxos", "uncommitted_entries": 50, "cluster_size": 5}
Response: {"type": "simulate_leader_change_cost_ok", "in_reply_to": 3, "messages_needed": 8, "rounds_needed": 1}Sample Test Cases
Side-by-side comparisonTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"compare_consensus","msg_id":2}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Raft leader change cost scales with uncommittedTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"simulate_leader_change_cost","msg_id":2,"protocol":"raft","uncommitted_entries":50,"cluster_size":5}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
Raft restricts log to be leader-driven with no holes; Paxos allows out-of-order slots
Hint 2▾
Raft leader change: new leader must replicate all uncommitted entries
Hint 3▾
Paxos leader change: only need Phase 1 for the next slot (cheaper)
Hint 4▾
Raft is designed for understandability; Paxos is designed for generality
Hint 5▾
Production systems: etcd uses Raft, Google Chubby uses Multi-Paxos
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
RaftMulti-Paxosmessage complexityleader change costunderstandability
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python3
import sys
import json
def main():
# Your implementation here
for line in sys.stdin:
msg = json.loads(line)
print(json.dumps(msg), flush=True)
if __name__ == "__main__":
main()