It was the first consensus algorithm proposed by L. Lamport in 1989. The objective was to choose a single value under the crash or network faults. We will look into the Paxos in a simplified view, and later we will try to understand how it can be implemented in a real system to ensure consensus.
The main idea behind the Paxos consensus algorithm is straightforward, and we will understand it with an example. Let us consider that we are at the college and after classes, we are going to hang out all together. We have two options to hang out with classmates after classes: Subway and Coffee Cafe Day (CCD). So after classes, we can either go to Subway or CCD based on the collective decision, but everyone will go to the same place. In this case, there is no central leader. The only way to take a collective decision is that a few of them (in this case, max could be the two students) will propose an option (i.e., CCS or Subway). Others will either accept or reject that proposed option, and the majority count will be the final value, which will be the consensus.
Paxos: Types of Nodes
There is a certain terminology used in PAXOS, and there are as follows: There are three types of nodes, the proposer, acceptor, and learner. However, everyone is a learner in the network who learns what the majority decision is.
- Proposer: The proposer proposes values, and the consensus algorithm should choose that proposed values.
- Acceptor: They form the consensus and accept the values. Whenever they hear a certain proposal from the proposer, the acceptors either accept or reject the proposal.
- Learner: This learner will determine which value has been chosen by each acceptor and collectively accept that particular value.
Making a Proposal: Proposer Process
The proposer initially prepares a proposal number so that this number needs to be good enough for the proposal to be accepted by the acceptors. The proposal number forms a timeline, and the biggest number considered up to date.
For example, there are two proposers P1 and P2, and P1 and P2 proposed values are 100 and 101. The acceptor always accepts a bigger proposal number, so in this case, it is P2 rather than P1.
Making a Proposal: Acceptor’s Decision Making
If the received proposal number is less or equal to the already seen or received proposal number, then it rejects else it accepts. It means the acceptor compares the recently received proposal number with the currently known values for all proposer’s received messages. If it gets the higher number, then it accepts; otherwise, it rejects.
Making a Proposal: Acceptor’s Message
Acceptor prepares the response, including accept or decline status, biggest proposal number, and accepted values. The acceptor can either accept or reject a message based on the proposed algorithm. The acceptor includes the biggest number that the acceptor has seen in the response message. It also includes the values that the acceptor has accepted to inform the proposer.
Accepting a value: Proposer’s Decision Making
The proposer looks for the response’s status, whether the majority of the acceptors reject/accept the proposal. If they have rejected the proposal, then the proposer updates with the latest proposal number. However, if most acceptors have accepted values, then the proposer cannot be chosen this value. In other cases, like the majority of acceptors accepted the proposal and this value was not chosen, then the proposer sends accept messages to others.
The basic idea is that whenever the majority of the acceptors send to accept the response. It means the value that the proposer has shared that is coming to be a consensus.
Accepting a Value: Accept Message
The final stage is accept message, the proposer sends the accept message to all the acceptors and in the accept message, the proposer includes the proposal number. A similar to the prepare phase, the proposal knows that his proposal has been accepted, and the value is the proposal’s single value.
Accepting a Value: Notifying Learner
Whenever the acceptor accepts a value from the proposer, it informs the learner about this is the majority voted value. So everyone learns that what is the majority voting in the environment.
Single Proposer: No Rejection
If there is a single proposal in the system, then the system is very simple, and with a single proposal, every acceptor will accept the proposal because that will be the biggest. So the proposal does not get rejected if the acceptors are correct. So we have to ensure that majority of acceptors are non-faulty.
Handling Failure: Acceptor Failure
Whenever a certain acceptor fails during the prepare phase, the system does not have any issue as the other acceptors can listen and vote either for or against the proposal. If the acceptor fails during the accept stage, the system does not have any issue because other acceptors are there who have already voted for the proposal. The only thing to ensure that the not more than N/2 number of acceptors fails simultaneously in the system. If that happens, then that violates the majority voting principle, and the system cannot come to a consensus.
Handling Failure: Proposer Failure
We will understand what happens when the proposer fails during the prepare phase or accept phase. If the proposer fails during the prepare phase, it is just like no one is proposing for any value, so the acceptor will keep on waiting for the state, and if they are not getting any value, others will become a proposer. It means, the acceptor waits for a certain duration, and if they do not receive any proposal, one of the acceptor becomes the proposal and propose a new value.
Suppose the proposal fails during the accept phase, the acceptors who have already agreed upon whether to choose or not choose the proposal value based on the majority vote. As they have already shared the majority vote among themselves, and from there, they can find out that whether the proposal has been accepted or not by the proposer.
Handling Failure: Dueling Proposers
There can be an interesting attack, which we called the dueling proposal. Let us consider, there are two proposals and the first proposer has sent a certain proposal to all the acceptors. Later, the second proposer has sent another proposal with the higher proposal number to all the acceptors. Again, the first proposer (an attacker) sees a proposal with a higher proposal number, and then she sent a higher proposal number. So it is like that whenever she sees that any other proposer has sent a proposal higher than her proposal number, she chooses a higher proposal number and sent to all the acceptors.
To break this tie, what other acceptors do, they block the proposer with a lower height. To do this, which particular proposer has a lower height, we need to execute a certain algorithm. We have a leader election algorithm. So this leader election algorithm can select one of the proposers as a leader as the Paxos is a consensus algorithm. Paxos itself can be used as a leader election algorithm.
The overall idea is that the proposer is proposing a certain opinion to all the acceptors and acceptors collectively look into the proposal. If they agree with the proposal, they send the accept message and receive that particular accept message. If the proposer finds out that his message has been accepted, then he sends back the accept message to all other acceptors. And from there, through the majority voting, they come to a consensus protocol.
The simple view of the Paxos is easier to understand, it is just like making one selection, but if we look into the real system, we may go for a sequence of selection choices rather than having a single choice. So that kind of system we call a multi-Paxos system. This multi Paxos system is something like make a sequence of choices by applying repeated Paxos protocol.
Applying repeated Paxos is something complicated because have all these messages need to be exchanged among each other again and again and which increases the complexity of the Paxos protocol so that is why although the Paxos gives a nice theoretical idea about why the system can reach a consensus, or how are distributed system can lead to a consensus. Indeed this Paxos protocol was the first that has proved that you can have a certain consensus algorithm in a distributed environment.
By applying this kind of proposal and acceptors accepting certain values, you can do a certain level of optimizations on top of this repeated Paxos, which is basically done in the case of multi Paxos to come to a consensus.
References
- NPTEL lecture series on Blockchains Architecture, Design and Use Cases by Prof. Sandip Chakraborty, IIT Kharagpur.
971 total views, 1 views today
