Ironically, the abstract of the paper ‘Paxos made simple’ says ‘The Paxos algorithm, when presented in plain English, is very simple.’ Unfortunately most of the Distributed Systems students fail to grasp this for the first few times. This blog makes an attempt to be a refresher for ‘Paxos Consensus Algorithm’ and provides handy reference to the crux of the consensus algorithm with some optional details towards the end.
Assume a collection of processes that can propose values. A consensus algorithm ensures that a single one among the proposed values is chosen.
• Only a value that has been proposed may be chosen,
• Only a single value is chosen, and
• A process never learns that a value has been chosen unless it actually has been chosen.
• Some proposed value is eventually chosen and, if a value has
been chosen, then a process can eventually learn the value.
• Processes operate at arbitrary speed, may fail by stopping, and may
restart. Since they may fail after a value is chosen and then
restart, a solution is impossible unless some information can be remembered by the process that has failed and restarted. Stable storage is required with every process.
• Messages can take arbitrarily long to be delivered, can be duplicated,
and can be lost, but they are not corrupted.
Proposer: Predetermined co-ordinator process. Also known as leader. Leader proposes values. In failure free case, there should be one leader.
Acceptors: Collection of processes cooperate to choose a value.
Phase 1
(a) A proposer selects a proposal number n and sends a prepare
request with number n to a majority of acceptors.
(b) 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.
Phase 2
(a) If the proposer receives a response to its prepare requests
(numbered n) from a majority of acceptors, then it sends an accept
request to each of those acceptors for a proposal numbered n with a
value v, where v is the value of the highest-numbered proposal among
the responses, or is any value if the responses reported no proposals.
(b) If an acceptor receives an accept request for a proposal numbered
n, it accepts the proposal unless it has already responded to a prepare
request having a number greater than n.
What is this algorithm exactly?