TASK
Implementation
The key advantage of 3PC over 2PC is that it unblocks one of 2PC's blocking scenarios. When the coordinator crashes after sending PreCommit, participants can proceed to commit without waiting for recovery.
2PC blocking scenario:
- Coordinator sends
Prepareto all participants - All participants vote
Yes - Coordinator crashes before sending
Commit - Participants are blocked: they don't know if the decision was Commit or Abort
- Participants must wait for coordinator recovery
3PC non-blocking scenario:
- Coordinator sends
CanCommitto all participants - All participants vote
Yes - Coordinator sends
PreCommitto all participants - All participants acknowledge
PreCommitand enterPRE_COMMITTEDstate - Coordinator crashes before sending
DoCommit - Participants are not blocked: they know everyone voted Yes, so they can commit
Recovery rules for participants in PRE_COMMITTED state:
function onTimeout() {
if (state === PRE_COMMITTED) {
// We know everyone voted Yes, so we can commit
commit();
broadcast("I have committed");
}
}Example test:
Request: {"type": "txn_begin", "msg_id": 1, "participants": ["p1", "p2"], "crash_coordinator_after": "pre_commit", "participant_timeout_ms": 2000}
Response: {"type": "txn_begin_ok", "in_reply_to": 1, "txn_id": "txn42"}
// After timeout, participants commit without coordinator:
{"type": "have_committed", "src": "p1", "txn_id": "txn42", "recovery": "timeout"}
{"type": "have_committed", "src": "p2", "txn_id": "txn42", "recovery": "timeout"}Sample Test Cases
3PC unblocks after PreCommitTimeout: 7000ms
Input
{"src":"c0","dest":"coord","body":{"type":"init","msg_id":1,"participants":["p1","p2"]}}
{"src":"c1","dest":"coord","body":{"type":"txn_begin","msg_id":2,"participants":["p1","p2"],"operations":[{"transfer":100,"from":"a","to":"b"}],"crash_coordinator_after":"pre_commit","participant_timeout_ms":2000}}
Expected Output
{"src": "coord", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
2PC blocks in same scenarioTimeout: 7000ms
Input
{"src":"c0","dest":"coord_2pc","body":{"type":"init","msg_id":1,"participants":["p1","p2"],"protocol":"2pc"}}
{"src":"c1","dest":"coord_2pc","body":{"type":"txn_begin","msg_id":2,"participants":["p1","p2"],"operations":[{"transfer":100,"from":"a","to":"b"}],"crash_coordinator_after":"prepare","participant_timeout_ms":2000}}
Expected Output
{"src": "coord_2pc", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
In 2PC, if coordinator crashes after all vote Yes, participants block forever
Hint 2▾
In 3PC, PreCommit phase lets participants know a commit is coming
Hint 3▾
If coordinator crashes after PreCommit, participants can commit without waiting
Hint 4▾
Participants in PRE_COMMITTED state can timeout and commit unilaterally
Hint 5▾
Show this with a test: crash coordinator after PreCommit, verify participants commit
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
blocking vs non-blockingrecovery procedurestimeout handlingcoordinator failureparticipant uncertainty
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()