Paxos algorithm:

This article explains the Paxos algorithm with reference to people as participants. A group of people wants 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 coordinated 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 to choose 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 proposals, 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 was accepted 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.