Overview
Paxos is an algorithm that solves the consensus problem in a network of faulty (unreliable) processors. Leslie Lamport developed the Paxos algorithm.
In simple terms, the Paxos algorithm focuses on making all the processors choose the same value that is requested by a client. Paxos algorithm lets the nodes agree on a value despite node failures, network failures, and network delays. The key idea is that a majority represents the whole — if more than half of the processes choose a value, that value is the consensus.
Paxos Algorithm is used in implementing replicated state machines, such as a distributed storage system. e.g., Chubby uses the Paxos algorithm to construct a fault-tolerant cell of five replicated machines.
Algorithm
The Paxos algorithm divides the processors into 3 groups - proposers, acceptors, and learners. The processors that take the client request and inform other processors about the same are called proposers. There is a unique value attached to every proposal (client's request). The processors that vote to choose the consent value are called acceptors. The processors that want to know what value is chosen are called learners.
There are two phases involved in the process.
Promise Phase (P)
In this phase, the processor (proposer) informs all other processors about the client's request, and the other processors (learners), on receiving the information, agree to the same if they are not reserved with any other value. The learners remember the approval of the request with the 'x' ID.
Commit Phase (C)
In this phase, the proposer sends a request to all others to commit the proposed ID = x to some value. The other processors (acceptors) accept the request and commit to that ID = x to the chosen value. This way, a consensus is reached.
Example
Example 1
Let's understand this with an example - 5 processors (people) - P1, P2, P3, P4, and P5, in the system.
They want to choose a movie. Let's say person 3 (P3) proposes movie C. Now the P3 generates a random ID for this request (movie C) - let it be 30 (can be anything) and sends a message to everyone (P1, P2, P4, P5), informing them about the request, with ID 30.
All of them receive the request (majority vote), accept it, send OK, and remember that they have promised P3 with the request ID 30. This is the end of the promise phase.
Now, P3 requests others to commit ID = 30 to movie C.
Others respond OK and remember that they have committed to ID=30 with the value = movie C.
Now, P3 knows that everyone has chosen movie C, and no other movie will be chosen. This is the end of the commit phase.
All of them have reached a consensus.
Example 2
Let's assume another case where person 2 (P2) and person 4 (P4) move out for a while (node failure).
P3 proposes to watch movie C and so sends the message to others with a request ID = 30.
Others (P1 and P5) receive the request, accept it, send OK, and remember that they have promised P3 with the request ID 30. Since P3 gets 3 votes (P1, P3, and P5), and 3 being the majority out of 5, P3 chooses to move ahead.
Now, P3 requests others to commit ID=30 to movie C.
Others (P1, P5, and P3) respond OK and remember that they have committed to ID=30 with the value = movie C. Now, P3 knows that everyone has chosen movie C, and no other movie will be chosen.
They have reached a consensus.
Example 3
Continuing the previous example, let's say now P2 and P4 come into the room (nodes become alive/wake up). Not knowing what has happened already, P2 proposes to watch movie B. So, P2 sends a message to everyone with a request ID = 20 (let).
P4 accepts the request (as it doesn't know that a value = movie C has already been chosen), sends OK, and remembers that he has promised P2 with request ID = 20. But since P1, P3, and P5, remember that they have promised to P3 with ID = 30 and value = movie C. So, P1, P3, and P5 compare the request ID from P2 = 20 to the earlier ID = 30. Since 20 < 30, P1, P3, and P5 reject the request (majority) and reply with NO.
A promise can only be broken to a request with a higher ID than the ID of the request one has already promised.
Since P2 did not get the majority vote, now, P2 generates a new ID (>20), let's say 40. Again, P2 sends a message to all others (P1, P3, P4, and P5) with a request ID = 40.
P4 accepts the request, sends OK, and remembers that he has promised P2 with request ID = 40.
Since 40 > 30, P1, P3, and P5 accept the request, send OK, along with the request ID = 30 and the value = movie C, telling P2 that they have already committed to ID = 30 with the value = movie C, and remember that they have promised P2 with request ID = 40.
So now, P2 gets to know that P1, P3, and P5 have already committed to ID = 30 with a value = movie C. So, P2, instead of sending a commit for movie B, rather sends a commit for movie A, requesting everyone to commit ID=40 to movie C.
Everyone responds OK and remembers that they have committed to ID=40 with the value = movie C. In this way, the previous consensus (movie C) is maintained.
Node failure cases
If the processor (proposer) fails before proposing, nothing happens, and some other processor becomes the proposer.
If the processor (proposer) fails after proposing since other nodes are yet to commit, nothing happens, and some other processor becomes the proposer, and the process restarts.
If the processor (proposer) fails after sending the commit request, in that case, if the other nodes have agreed on some value, some other node will do the task(similar to the case where P2 and P4 go out of the room), and the consensus would be maintained. Otherwise, if there is no majority agreement on that proposed value, some other node would become the proposer, and the process restarts. In this case, the client would wait for some time and then probably ask some other node for the value (e.g., a lock).
If the processor (proposer) fails after accepting the commit request, nothing happens, as every node has already come to an agreement (reached a consensus).