Paxos

paxos

A collection of process can propose values A consensus algorithm ensures

• That a single proposal is chosen

• The processes can learn the proposed value

• No value is chosen if there are no proposals.

• what: consensus probelm algorith.

• how:

  • Prepare:propersor sends a Prepare message containing this proposal to a Quorum of Acceptors
  • Promise:If the proposal's number N is higher than any previous proposal number received from any Proposer by the Acceptor, then the Acceptor must return a promise to ignore all future proposals having a number less than N. If the Acceptor accepted a proposal at some point in the past, it must include the previous proposal number and previous value in its response to the Proposer.
  • Accept request:If a Proposer receives enough promises from a Quorum of Acceptors, it needs to set a value to its proposal. If any Acceptors had previously accepted any proposal, then they'll have sent their values to the Proposer, who now must set the value of its proposal to the value associated with the highest proposal number reported by the Acceptors. The Proposer sends an Accept Request message to a Quorum of Acceptors with the chosen value for its proposal.
  • Accepted:If an Acceptor receives an Accept Request message for a proposal N, it must accept it if and only if it has not already promised to only consider proposals having an identifier greater than N. In this case, it should register the corresponding value v and send an Accepted message to the Proposer and every Learner. Else, it can ignore the Accept Request.