Implement Paxos Commit Protocol - The Coordinator

                      TASK
                    

Implementation

Paxos Commit replaces the single coordinator with a Paxos consensus group. Each participant's commit decision is reached through Paxos, eliminating the single point of failure.

Architecture:

Each participant has its own Paxos instance deciding its commit/abort vote
A proposer proposes "commit" or "abort" to each Paxos instance
Once a value is chosen by Paxos, it cannot be undone
No single coordinator failure point

Paxos phases for commit:

For each participant P:
  Phase 1a (Prepare):  proposer → acceptors: Prepare(1)
  Phase 1b (Promise):  acceptors → proposer: Promise(1, prev_value_if_any)
  Phase 2a (Accept):   proposer → acceptors: Accept(1, "commit")
  Phase 2b (Accepted): acceptors → proposer: Accepted(1, "commit")

Example Paxos Commit:

Request:  {"type": "paxos_commit_begin", "msg_id": 1, "participants": ["p1", "p2", "p3"], "acceptors": ["a1", "a2", "a3"], "operations": [{"transfer": 100, "from": "a", "to": "b"}]}

// Phase 1 for p1's decision:
{"type": "prepare", "msg_id": 2, "proposal_id": 1, "participant": "p1"}
{"type": "promise", "in_reply_to": 2, "acceptor": "a1", "proposal_id": 1, "accepted_value": null}
{"type": "promise", "in_reply_to": 2, "acceptor": "a2", "proposal_id": 1, "accepted_value": null}
{"type": "promise", "in_reply_to": 2, "acceptor": "a3", "proposal_id": 1, "accepted_value": null}

// Phase 2 for p1's decision:
{"type": "accept", "msg_id": 3, "proposal_id": 1, "participant": "p1", "value": "commit"}
{"type": "accepted", "in_reply_to": 3, "acceptor": "a1", "proposal_id": 1, "value": "commit"}
{"type": "accepted", "in_reply_to": 3, "acceptor": "a2", "proposal_id": 1, "value": "commit"}
{"type": "accepted", "in_reply_to": 3, "acceptor": "a3", "proposal_id": 1, "value": "commit"}

// Repeat for p2, p3...

Advantages over 2PC/3PC:

No single coordinator failure point
Tolerates crash of any proposer (any proposer can retry)
Non-blocking as long as a majority of acceptors is available

Disadvantages:

Higher latency: 2 round trips per participant
Higher message complexity: 4N messages per participant
More complex implementation

Sample Test Cases

Successful Paxos commitTimeout: 10000ms

Input

{"src":"c0","dest":"paxos_coord","body":{"type":"init","msg_id":1,"participants":["p1","p2","p3"],"acceptors":["a1","a2","a3"]}}
{"src":"c1","dest":"paxos_coord","body":{"type":"paxos_commit_begin","msg_id":2,"participants":["p1","p2","p3"],"acceptors":["a1","a2","a3"],"operations":[{"transfer":100,"from":"a","to":"b"}]}}

Expected Output

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

Proposer crash recoveryTimeout: 10000ms

Input

{"src":"c0","dest":"paxos_coord","body":{"type":"init","msg_id":1,"participants":["p1","p2"],"acceptors":["a1","a2","a3"]}}
{"src":"c1","dest":"paxos_coord","body":{"type":"paxos_commit_begin","msg_id":2,"participants":["p1","p2"],"acceptors":["a1","a2","a3"],"operations":[{"transfer":100,"from":"a","to":"b"}],"crash_proposer_after":"prepare"}}
{"src":"c2","dest":"paxos_coord","body":{"type":"recover_proposer","msg_id":3}}

Expected Output

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

Hints

Hint 1▾

Replace the coordinator with a Paxos group (acceptors)

Hint 2▾

Each participant's vote is decided by its own Paxos instance

Hint 3▾

Phase 1 (Prepare): proposer gets promises from acceptors

Hint 4▾

Phase 2 (Accept): proposer sends value, acceptors accept if promised

Hint 5▾

No single point of failure: any proposer can drive the protocol

Resources

Paxos Made Simple

Original Lamport Paxos paper

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

Paxos commitconsensus-based commitno single point of failureacceptorsproposerslearners

main.py

python