TASK
Implementation
Implement a simplified PBFT (Practical Byzantine Fault Tolerance) with 4 nodes (f=1 Byzantine fault).
PBFT Three-Phase Protocol:
- Pre-prepare: Primary assigns sequence number, broadcasts (pre-prepare, v, n, d) to all
- Prepare: Each replica broadcasts (prepare, v, n, d, i) to all. Prepare-certificate = 2f matching prepares
- Commit: Each replica broadcasts (commit, v, n, d, i) to all. Commit-certificate = 2f+1 matching commits
Request: {"type": "pbft_request", "msg_id": 1, "operation": "set x=42", "client": "c1"}
Response: {"type": "pbft_request_ok", "in_reply_to": 1, "sequence_number": 1, "view": 0, "phase": "pre-prepare"}
Request: {"type": "pbft_status", "msg_id": 2, "sequence_number": 1}
Response: {"type": "pbft_status_ok", "in_reply_to": 2, "phase": "committed", "prepares_received": 3, "commits_received": 4, "executed": true}Sample Test Cases
Request starts pre-prepare phaseTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2","n3","n4"]}}
{"src":"c1","dest":"n1","body":{"type":"pbft_request","msg_id":2,"operation":"set x=42","client":"c1"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Status shows execution after all phasesTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2","n3","n4"]}}
{"src":"c1","dest":"n1","body":{"type":"pbft_request","msg_id":2,"operation":"set x=1","client":"c1"}}
{"src":"c1","dest":"n1","body":{"type":"pbft_status","msg_id":3,"sequence_number":1}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
PBFT uses 3 phases: Pre-prepare, Prepare, Commit
Hint 2▾
Pre-prepare: primary broadcasts the request to all replicas
Hint 3▾
Prepare: each replica broadcasts Prepare to all other replicas. Wait for 2f matching Prepares
Hint 4▾
Commit: each replica broadcasts Commit. Wait for 2f+1 matching Commits
Hint 5▾
With f=1 Byzantine fault, need N=4 nodes (3f+1=4)
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
PBFTpre-preparepreparecommitthree-phase protocol
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()