Paxos Algorithm

The Paxos algorithm is a consensus algorithm for a fault-tolerant distributed system. A consensus algorithm ensures that a single one among the proposed valued is selected. In Paxos, there are three types of agent: proposers, accepters, learners.

The algorithm runs as follows:

1. A proposer selects a proposal number (integer) n and sends to a majority of acceptors. This is called a 'prepare' request. Here majority means greater than half of the acceptors. If an acceptor receives a 'prepare' request with number n greater than that of any 'prepare' request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.

2. If the proposer receives a response to its prepare requests from a majority of acceptors, it send an 'accept' request to each of those acceptors for a proposal for a proposal numbered n with a value v. The v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals. If an acceptor receives an 'accept' request numbered n, it must accept it if and only if it has not already promised to only consider proposals having an identifier greater than N.

3. Each acceptor responds to all learners whenever it accept a proposal.