Paxos is an algorithm to solve the consensus problem in the distributed system. Consensus involves multiple servers in the distributed environment agreeing on values. These values we want to get consensus can be a real number (e.g., Master node ID in the leader election problem), a Log (log replications) or multiple logs (database transaction logs). Paxos is trying to make sure that the values are consensus among multiple machines even some machines fail.
At first, we introduce two terms before we go into the detail of the paxos algorithm.
Process: one of the machine in the system
Client: a machine who isn’t a part of the system, is the one who asking what the value is or asking to write a new value in the system.
Now, we illustrate the paxox in the following two aspects: Reading and Writing.
To read a value from the system, a client asks all processes in the system that what is the current value, then the client takes the value agreed by majority of the processes. We can see that the system work once more than half the machines still works and some machines own the out-of-the-date values will not impact the result.
Writing consists of 2 phases:
First phase, the client will contract one process in the system and tell the process one value. We call this process the proposer. The proposer will broadcast the value to all the other processes in the system. The proposal is labelled with a unique sequence number. Highest number indicates the latest value. Once each other process receives the proposal, it will compare the number with the largest number received so far. If it is the largest, it means the value is the latest one. This process will accept this value. Otherwise, it will reject the proposal and tell the proposer the latest value and its corresponding sequence number.
Second phase, after the proposer get the responses from majority of the processes, no matter the other node accept or reject the proposal of the proposer process, the proposer knows the latest value and the sequence number. It will send the accept message to those responding processes. The message contain the latest value and the sequence number. The process receives the accept message, if it find that the sequence number is the largest, it will accept it. Otherwise, it means the value proposed by the proposer is not the latest value. Therefore, the process will tell the proposer will restart the proposal process with the latest value.
The slides from stanford is a very good introduction on paxos. https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pdf
The basic process is shown in the Figure