Implement Paxos Phase 2 (Accept/Accepted) - The Consensus

                      TASK
                    

Implementation

Implement Phase 2 of Paxos. After getting a majority of promises in Phase 1, the proposer sends Accept(n, v) to acceptors.

Value selection rule: if any promise included a previously accepted value, the proposer MUST use the value with the highest accepted_n. Otherwise, the proposer chooses freely.

Request:  {"type": "paxos_accept", "msg_id": 1, "proposal_n": 5, "value": "consensus_value"}
Response: {"type": "paxos_accepted", "in_reply_to": 1, "accepted": true, "proposal_n": 5, "value": "consensus_value"}

Request:  {"type": "paxos_accept", "msg_id": 2, "proposal_n": 3, "value": "late_value"}
Response: {"type": "paxos_accepted", "in_reply_to": 2, "accepted": false, "reason": "promised_higher", "highest_promised": 5}

Request:  {"type": "paxos_chosen", "msg_id": 3}
Response: {"type": "paxos_chosen_ok", "in_reply_to": 3, "value": "consensus_value", "chosen_at_n": 5}

Sample Test Cases

Accept succeeds after promiseTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"paxos_prepare","msg_id":2,"proposal_n":5}}
{"src":"c1","dest":"n1","body":{"type":"paxos_accept","msg_id":3,"proposal_n":5,"value":"hello"}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "paxos_promise", "in_reply_to": 2, "promised": true, "accepted_n": null, "accepted_value": null, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "paxos_accepted", "in_reply_to": 3, "accepted": true, "proposal_n": 5, "value": "hello", "msg_id": 2}}

Accept rejected for lower proposalTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"paxos_prepare","msg_id":2,"proposal_n":5}}
{"src":"c1","dest":"n1","body":{"type":"paxos_accept","msg_id":3,"proposal_n":3,"value":"old"}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "paxos_promise", "in_reply_to": 2, "promised": true, "accepted_n": null, "accepted_value": null, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "paxos_accepted", "in_reply_to": 3, "accepted": false, "highest_promised": 5, "msg_id": 2}}

Hints

Hint 1▾

Phase 2: Proposer sends Accept(n, v) to acceptors

Hint 2▾

v = highest accepted_value from Phase 1 promises, or proposer choice if none

Hint 3▾

Acceptors accept if n >= highest_promised

Hint 4▾

Once a majority accepts, the value is chosen (consensus reached)

Hint 5▾

A chosen value can never be changed by future proposals

Resources

Understanding Paxos

Step-by-step walkthrough of the Paxos protocol phases

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

PaxosAcceptAcceptedvalue selectionconsensus

main.py

python