Paxos acceptors preserve promises and accepted proposals across protocol messages. A proposer can move forward only when enough acceptors promise not to accept older proposals.
Design a PaxosAcceptor class:
PaxosAcceptor() creates an acceptor with no promise and no accepted proposal.int[] prepare(int proposalNumber) processes a Phase 1 prepare request.boolean accept(int proposalNumber, int value) processes a Phase 2 accept request.int[] accepted() returns the currently accepted [proposalNumber, value], or [-1, -1] when none exists.
The acceptor stores promised, acceptedProposal, and acceptedValue, all initially -1.
For prepare(n):
- If
n > promised, set promised = n and return [1, acceptedProposal, acceptedValue]. - Otherwise, reject it and return
[0, acceptedProposal, acceptedValue].
For accept(n, value):
- If
n >= promised, store promised = n, acceptedProposal = n, and acceptedValue = value, then return true. - Otherwise, return
false without changing any state.
Proposal numbers are globally unique, so one proposal number is never used with two different values.
Example 1:
Input:
Output:
Explanation: Prepare 10 establishes the promise. The matching accept request is allowed and records value 42.
Example 2:
Input:
Output:
Explanation: The higher prepare reports the accepted proposal and value. It does not erase them. Once proposal 8 is promised, prepare 6 is rejected.
Constraints
0 <= proposalNumber <= 10^9-10^9 <= value <= 10^9- Proposal numbers are globally unique and permanently identify one value.
- At most
10^5 method calls are made per object. - Every returned array must be independent of the acceptor's internal state.
Implement a Paxos Acceptorhard