This is the fifth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

The basic concept

Paxos protocol is one of the few decentralized and distributed protocols with strong consistency and high availability proven in engineering practice
The Paxos protocol process is more complex, but the basic idea is similar to the voting process
PaxosA protocol has a set of fully peer participating nodes:acceptor
- Each group of nodes makes a decision about something, and a decision takes effect if more than half of the nodes agree on it
Paxos protocol can work as long as more than half of the nodes are normal, and it is good against downtime, network fragmentation and other anomalies

role

Proposer:The plan
- A Proposer can have more than one
- ProposorIntroduced legislationvalue:
  - value:13. Refers to any operation in engineering practice:
    - Like changing a variable to a value
    - Set the current primary to a node, and so on
  - These operations are abstracted as values in Paxos
- differentProposerCan put forward different or even contradictoryvalue:
  - For example, a Proposer says, “Set variable X to 1.”
  - Another Proposer proposes “setting variable X to 2”
- However, for the same Paxos process, only one value can be approved at most
Acceptor:approver
- There can be more than one Acceptor
- A numbered value submitted by a Proposer must be approved by a majority of acceptors
- Acceptors are completely independent of each other
Learner:Learners’
- LearnerStudy approvedvalue:
  - That is, by reading each Proposer’s selection of values
  - If a value is accepted by more than half of acceptors, the user learns about the value
Similar to Quorum, a value needs to be approved by N2+1\frac{N}{2}+12N+1 acceptors, and learners should read at least N2+1\ FRAc {N}{2}+12N+1 acceptors. A value that passes can be learned only after the results of N acceptors are read
These three roles are only logically divided, and a node can play these three roles simultaneously in engineering practice

The Paxos protocol goes round by round, and each round has a number. Each Paxos round may approve a value. If a value is approved in a Paxos round, only this value can be approved in subsequent rounds
Each round of protocol flow constitutes a Paxos instance. Only one VALUE can be approved by a Paxos instance. This is also an important reflection of the strong consistency of the Paxos protocol
Each roundPaxosThe agreement is divided into two phases:
- Preparation stage
- Approval stage
- The phase Proposer and Acceptor have their own processes

Send the Prepare(b) message to all acceptors, where b is the number of Paxos rounds
If you receive any of themAcceptorSent message“Reject” (B),For thisProposerIn terms of epicyclePaxosFailure will be the number of roundsbSet toB+1Then repeat the previous step
- During the approval phase, different choices are made based on Acceptor messages received
If you receiveAcceptorthe“Promise” (b, v_i)The message to $\frac{N}{2}+1$ a. NforAcceptorThe total, the division is rounded,v-isaidAcceptorThe last timeiRound approvedvalue
- If v is null in any of the “Promise(b, v) messages received, the Promise selects a value as v and broadcasts the Accept(b, v) message to all acceptors.
- Otherwise, select the maximum value of I from all received Promise(b, v_i) messages as v and broadcast the Accept(b, v) message to all acceptors.
If Nack(B) is received, set the number of rounds B to B+1 and repeat the first step

To receive aProposerThe news of thePrepare(b).parameterBIs that theAcceptorMaximum receivedPaxosRound number number,VisAcceptorApproved by thevalue,Can be null
- If b > b, reply with Promise(b, V_B) and set b = b. Indicates that proposals numbered less than B are no longer acceptable
- Otherwise, reply with “Reject(B) Message.”
acceptAccept(b, v):
- If b < b, reply Nack(b) indicating that a Proposer with a greater number was accepted by the Acceptor
- Otherwise, set V= V to indicate that the Acceptor approves a Value of V. Broadcast “Accepted Message”

There are five acceptors and one Proposer with no network
Changes to variables B and V on acceptors and to variables B on Proposer are investigated
Initial state:

Proposer sends “Prepare(1)” to all acceptors. All acceptors handle this correctly and reply to the Promise(1, NULL) :

(a) a Proposer receives five promises (1,NULL) with values that satisfy more than half of those promises, and sends Accept(1, v1) where v1 is the Proposer’s numbered value:

At this point,v1 has been approved by more than half of acceptors, and v1 is the value approved by the Paxos instance. If Learner learns value, he can only learn V1
PaxosThe heart of the agreement: The approved value cannot be changed.This is also the basis of the correctness of the whole protocol
- An approved value cannot be changed within the same Paxos instance, even if a subsequent Proposer initiates a Paxos protocol with a higher numbered number
PaxosProtocols are artificially designed, and the design process is also the derivation of protocols:
- The Paxos protocol utilizes the Quorum mechanism, selecting W=R=N2+1W=R=\frac{N}{2}+1W=R=2N+1
- If a Proposer updates more than half of its acceptors successfully, then the update succeeds
- Learner reads acceptors according to Quorum, and if a value is successfully read on more than half of the proposers, it is an approved value
- The protocol avoids deadlocks by introducing rounds so that the proposal of high rounds preempts the proposal of low rounds
Key points of protocol design:
- How to satisfy the constraint that “Only one value is approved during a Paxos algorithm instance”