Implement Single-Decree Paxos Phase 1 (Prepare/Promise) - The Consensus

                      TASK
                    

Implementation

Implement Phase 1 of single-decree Paxos (agree on one value).

Phase 1 (Prepare/Promise):

Proposer selects a unique proposal number n
Proposer sends Prepare(n) to all acceptors
Each acceptor: if n > highest_promised, set highest_promised = n and reply Promise(n, accepted_value, accepted_n)
If n <= highest_promised, reject

Request:  {"type": "paxos_prepare", "msg_id": 1, "proposal_n": 1}
Response: {"type": "paxos_promise", "in_reply_to": 1, "promised": true, "accepted_n": null, "accepted_value": null}

Request:  {"type": "paxos_prepare", "msg_id": 2, "proposal_n": 5}
Response: {"type": "paxos_promise", "in_reply_to": 2, "promised": true, "accepted_n": null, "accepted_value": null}

Request:  {"type": "paxos_prepare", "msg_id": 3, "proposal_n": 3}
Response: {"type": "paxos_promise", "in_reply_to": 3, "promised": false, "reason": "already_promised_higher", "highest_promised": 5}

Sample Test Cases

First prepare is always promisedTimeout: 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":1}}

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}}

Higher proposal supersedes lowerTimeout: 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_prepare","msg_id":3,"proposal_n":3}}

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_promise", "in_reply_to": 3, "promised": false, "highest_promised": 5, "msg_id": 2}}

Hints

Hint 1▾

Phase 1: Proposer picks a unique proposal number n and sends Prepare(n) to acceptors

Hint 2▾

Acceptors respond with Promise(n, previously_accepted_value) if n > their highest seen

Hint 3▾

If acceptor has already promised a higher n, it rejects the Prepare

Hint 4▾

Proposal numbers must be globally unique (use node_id + sequence)

Hint 5▾

A proposer needs promises from a majority to proceed to Phase 2

Resources

Paxos Made Simple - Lamport

Leslie Lamport simplified explanation of the Paxos algorithm

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

Paxossingle-decreePreparePromiseproposal number

main.py

python