This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together.

Paxos algorithm

Paxos algorithm is an algorithm to solve the problem of data consistency in distributed systems. It is a very important algorithm in distributed systems. Mike Burrows, the author of Google Chubby, said that there is only one consistency algorithm in the world, that is Paxos, and other algorithms are inferior. This shows the importance of this algorithm.

The Paxos algorithm classifies the roles in the system into three types: Proposer (Acceptor) and Learner (Learner).

  • (a) a Proposer (proposals) The content of a Proposal can include a Proposal ID and a Value.
  • A Proposal submitted by an Acceptor automatically agrees to the latest Proposal.
  • Learner: Learns the most recent agreed proposals from proposers /Acceptors

The Paxos algorithm is divided into two phases by a resolution, so it is a 2PC protocol.

Stage 1:
  1. A Proposer sends a Prepare request numbered N to more than half of its Acceptors
  2. If an Acceptor receives a Prepare request with number N greater than the number of all Prepare responses received, It then reports back to the Proposer with the largest number it has approved as a response, promising not to approve any proposal with a number less than N.
Stage 2:
  1. (a) If a Proposer receives a majority of the Acceptors’ commitments, it sends an Acceptor a proposal containing the number N of the previous phase and a proposal Value returned by the Acceptors at the previous phase. If no proposal is numbered, it determines the Value of the proposal.
  2. An Acceptor receives an Acceptor proposal numbered N with the value V. This Acceptor will accept the proposal as long as no number greater than N has been accepted.

When more than half of acceptors accept the proposal, the represented Learner learns, which is then sent to other Learner nodes for learning.

So that’s the end of Paxos, and I’ll use a simple example to illustrate.

If one class is going on a spring outing, the monitor asks the class for advice on where to go. At this time, the role of class cadres is the decision maker, the class students are the proposer.

Student A put forward proposal 1- park. No one put forward A new proposal at this time. Then the decision maker will automatically agree to the proposal.

Then student B put forward proposal 2 — the zoo, according to the Paxos algorithm, will automatically approve the latest proposal, so the proposal will also be approved.

If there is no proposal from the next class, it will be decided to go to the zoo. Then the whole class was informed that the destination of the spring outing was the zoo.

The live lock problem of Paxos algorithm

This is a simple case. But this algorithm has a live lock problem. Because each Proposer can make a proposal. So there could be an election without a bill being put on the floor.

Take the above case as an example. After student B put forward proposal 2, student C put forward proposal 3 — Ocean Park. Before the final implementation of the proposal, student A put forward proposal 4 — amusement park. If acceptors accept a Proposer no more than a phase 2 numbered proposal (Proposer), a phase 3 numbered proposal (Proposer) with a phase 3 numbered proposal (Proposer) is not accepted. The Paxos algorithm is that acceptors make commitments to a phase 3 numbered proposal.

There are two solutions to this problem. The first proposal includes a “cooling off” period for each Proposer to wait before sending a prepare request. The Proposer would then have been approved by half of the decision makers.

Another scheme is to elect a Leader among the proposers, who will issue proposals to the decision maker, so that proposals will not be issued all the time.