Paxos is a consensus algorithm in distributed systems. The consensus algorithm is an algorithm that determines (agrees on) a single value within a network of multiple nodes.
In a phrase, Paxos wants to determine a single value that will not be overturned. Specifically, computers that are independent of each other (do not share memory) and exchange information only through the network participate in the consensus, and if a majority of them choose the same value, them all learn that value and it cannot be overturned.
Paxos is desigined to work well even if communication massages are lost or computers fail. Therefore, if a communication parther does not reply to a message, it is impossible to determine whether the communication is slow, the parthner is malfunctioning, or the message has been lost. This is called the asyncronous communication model in distributed systems.
The algorithm is difficult to understand. That's why we deal with specific examples. Look at the following images Captuer of Youtube Video.
When the value proposer wants to decide on a value, a Propose message is sent to everyone.This is assigned a monotonically increasing proposal number.
The acceptor checks the current received proposal number and the maximum proposal number it has received in the past. If the current received proposal number is larger, the acceptor takes one of the following actions
① If there is no previously accepted value, the proposer replies prepare message.
② If there is already another accepted value, reply with a received message including that value.
① If a prepare message is received from an acceptor, the proposer sends an acceptance request of any value to that acceptor.
② If a received message is received, check the previously received values contained in that message. It then overwrites the value the proposer wishes to propose with that value and sends a request for acceptance of that value.
The acceptor learns the values sent by the proposer.
As we have described, the Paxos algorithm can be used to determine a single uncovered value among distributed nodes connected by an asynchronous channel. This underlying algorithm is the basis for such algorithms as Multi-Paxos, which determines the order of execution of state machine replications (SMRs).
Thanks for reading all the way to the end!