Paxos algorithm:
This article explains Paxos algorithm with reference to people as participants. A group of people want to come to a consensus with their choice of proposals. Paxos helps them arrive at this consensus eventually even when things go wrong. It guarantees that only one of the proposals will be chosen if at all and when it is chosen, all the others will be able to learn the choice and use it. If no proposals are made then there will not be any selection. The selection here is the end result of the algorithm so that all the participants can proceed in a co-ordinated manner knowing that there is only one common choice by consensus.
Paxos relieves the participants from figuring out how the choice is made until they are each informed of the choice. When there are proposals, there is a guarantee that a choice will be made and that it will eventually be communicated to the participant.
In this regard, each participant works in three modes: as a proposer, an acceptor and a learner. A proposer can make a proposal. As an acceptor, a participant makes the choice among proposals. Eventually as a learner, a participant knows which choice was made by itself or others. Participants inform each other with messages.
There are many failures that are overcome by this algorithm. Participants may not all be working in the same manner and at the same speed. They may disappear after a choice was made. Their messages may be lost, duplicated, or delivered very late. However, the messages are tamper-proof.
Since participants may not be reliable, this algorithm differs from others that require them to be available. It helps choosing a value in one of several approaches. The first approach is when a single participant decides which proposal to make or accept. Any one of the participants can be designated as the sole acceptor. Another approach is to involve more than one participant in a set of acceptors. In such a mode, a majority is chosen.
An acceptor may choose the first proposal made in the order of their arrival. In a set of acceptors with multiple messages arriving simultaneously, there might not be a majority among the acceptors. Acceptors may have to make more than one choice.
In order to keep track of different proposal, a tuple of a proposal sequence number and proposal is chosen. If the proposals are different, they have different numbers. If a single proposal is chosen, it has acceptance by the majority of the acceptors.
If a choice is made with a proposal, every higher numbered proposal uses this choice which allows acceptors to make more than one choice but guarantee that there is only one choice by consensus. Since there has to be at least one acceptor, a single choice will be guaranteed to be made.
