This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Paxos is a highly fault-tolerant consistency algorithm based on message passing proposed by Lellis-Lambert in 1990. It is one of the most effective algorithms to solve distributed consistency.

I. Source of Paxos

In 1982, Lambert and two others published The Byzantine Generals Problem, proposing a theory of computer fault tolerance known as The Byzantine Problem:

The Byzantine Empire had many armies, and the different armies had to make a unified plan of action to decide whether to advance or retreat. Moreover, the armies were geographically separated and relied on military correspondents to communicate. However, there may be traitors in the communicator, and the message may be tampered with in the process. How to ensure the consistency of the message in the communication process?

Because most of our distributed systems are on lans, message tampering is uncommon. We usually work on the assumption that the Byzantine problem doesn’t exist.

In 1990, Lambert proposed a theoretical consistent solution, along with a rigorous mathematical proof. Similar to the Byzantine problem, this algorithm is described in the form of a story:

In ancient Greece, there was a small island called Paxos, where laws were passed in the form of a council. Members of Parliament send messages through couriers. It is worth noting that both MPS and couriers are part-time and leave the chamber at any time, setting up couriers to deliver messages that may be repeated or never come back. Therefore, the parliamentary agreement requires that in such cases the statute can be guaranteed to be produced correctly and without conflict.

The Paxos algorithm takes its name from the island.

Lambert’s admittedly obscure description of the algorithm wasn’t accepted until 1998, when Paxos was accepted by computer scientists to solve the problem of consistency in distributed systems.

In 2001, Lambert released Paxos Made Simple, a retelling of the algorithm in plain English.

Second, algorithm analysis

2.1 Problem Description

Suppose there is a set of processes that can contribute proposals, then for a consistency algorithm the following points need to be guaranteed: 1) Of these proposed proposals, only one can be selected. 2) If no proposal is made, no proposal will be chosen. 3) If a proposal is selected, the process should have access to the selected proposal information.

The security conditions are as follows: 1) Only the proposed proposal can be selected. 2) Only one value is selected. 3) If the process thinks the proposal is selected, then the proposal is indeed selected.

In Paxos’s algorithm, there are three roles: 1) proposer, 2) acceptor, and 3) learner

2.2 Selection of proposals

Accept multiple acceptors for proposal selection. A single acceptor has a single point problem. How do you think this proposal has been chosen? Suppose there is a set of acceptors. If multiple acceptors have selected the proposal, the proposal is considered successful when the number of acceptors reaches a certain level.

On the whole, it is an algorithm execution process similar to two-stage submission:

Phase 1: A proposer sends a prepare request numbered M(n) to more than half of the acceptors. If an acceptor receives a proposal numbered M(n) greater than the number of proposals to which it responded, it sends the highest numbered proposal to the proposer as a response, promising not to accept any proposal numbered less than M(n).

If the proposer receives a response numbered M(n) from more than half of its acceptors, it sends an Accept request for a proposal numbered M(n). 2. If an acceptor receives an Accept request for the [M(n),V(n)] proposal, it can Accept the proposal as long as the acceptor has not yet responded to a prepare request greater than M(n).

2.3 Access to proposals

How to get learner to pass the proposal? The following schemes can be used:

Have all acceptors send their proposals to a single learner, who communicates with each other. Usually the main learner notifies the other learner.

The above scheme has the single point problem of the main learner, so a set of learner is needed.

A proposer selects a proposer to ensure the algorithm is active

A distributed algorithm usually has two key characteristics, security (guaranteed not to happen) and activity (guaranteed to happen).

If any of the proposers can submit a proposal, then based on the previous implementation, the algorithm will loop forever.

For example, an acceptor accepts and responds to a prepare request submitted by AN acceptor for M1. When A initiates a proposal in the second phase and finds that M1 is discarded, another PREPARE request for M3 will be issued, resulting in an endless loop.

If a proposer does not prepare a proposer with a majority of acceptors, then its proposals are accepted. When a proposer finds that there is currently a larger proposal, it drops the smaller proposal and eventually selects a larger proposal.

Third, summary

Paxos introduced the concept of majority rule. Paxos supports rotation of node roles to avoid distributed single points.

It is one of the best distributed algorithms.

“Welcome to the discussion in the comments section. The excavation authorities will draw 100 nuggets in the comments section after project Diggnation. See the event article for details.”