Consensus algorithm: Paxos algorithm

1. The directory

[TOC]

2. Consensus issues^Question

• What are consensus issues?

Roughly speaking, the problem is getting processes to agree on what a value should be after one or more processes have suggested it.

• Solve what problem?
• After one computer suggests an action, all the computers controlling the engine decide to “go ahead” or “give up.”
• In mutual exclusion, processes agree on which process can enter a critical section.
• In an election, the process comes to terms with the election process.
• In full-sorted multicast, processes agree on the order in which messages are delivered.

2.1 An example: Problem description^Example

If you have two (or more) armies, they must attack or defend at the same time, or they will lose. All the armies form a system, and they must act together. The question is, how do you keep them on the same page?

Now think of the military as a “process,” and attack or defense as a variable “action.”

• On stand-alone systems, this problem is easily solved. It’s done with a mutex, similar to multithreading.

• In distributed systems, this is a problem. Given that each process is on a different server, they cannot be synchronized through shared memory. If the process is military, the military can only communicate with each other through the signalman (messaging). Distributed military systems based on messaging have these problems:

1. How do you know if another army has been killed? (Server crashes)
2. How do YOU know if the signalman was killed (message lost) or took too long to reach another army (delay unpredictable)?
3. What if communication channels such as roads are cut off? (Network segmentation)

2.2 Another example

In a distributed database system, if the initial state of the nodes (servers, or processes) is consistent and each node performs the same sequence of operations, they can end up in a consistent state. In order to ensure that each node executes the same command sequence, it is necessary to execute a “consistency algorithm” on each instruction to ensure that each node sees the same instruction, which is an important problem in distributed computing.

3. Consistency principle of Paxos^{Paxos-Lamport}

• Nothing bad can happen

1. Only proposed values are selected;
2. Only one value can be approved, and no second value can overwrite the first;
3. Each node can learn only approved values, not unapproved values.

• Liveness (Good things will happen eventually)

1. Eventually a proposed value is approved;
2. A value is approved, and other processes eventually learn the value.

Paxos only guarantees Safety, not Liveness.

4. Paxos algorithm description

4.1 assuming that^{Paxos-Lamport}

Each server has three roles: Proposer, Acceptor, and Learner. The proposer is responsible for making the proposal, the receiver is responsible for approving the proposal, and the learner is responsible for updating the proposal.

Each proposal is assigned a natural number, NNN, as the ID, and a value, VVV, that needs to be presented.

4.2 Choosing a Value^{Paxos-Lamport}

Phase i. a. The proposer chooses a proposal number NNN and sends a prepare request to the majority of the recipients. B. If a receiver receives a prepare request whose number NNN is the largest of all the prepare requests he has already passed, he agrees to the new prepare request and promises not to agree to any prepare or Accept requests smaller than NNN.

Phase 2A. If the proposer receives a prepare_OK (n, NA, VA) response from a recipient majority, then he selects the vAV_ava corresponding to the largest nan_ana. Or, if vAV_AVA is empty in all responses, that is, no proposal has been agreed to yet, choose your own VVV. Then send the * Accept (n,v)* request. B. If a receiver receives an Accept (n,v) request and NNN is greater than all the NPN_PNP it prepared for, it accepts the VVV and replies to accept_OK (n).

4.3 Learning a Chosen Value

When a proposal is approved by the majority, the proposer sends a decided(V) to all servers to implement and implement the VVV.

4.4 Paxos pseudocode^Code

# Proposer proposer(v): while not decided: N = Heigher (n [:]) # Attempt to assign a current maximum value of n to the proposal Send prepare(n) # If most of the acceptors return OK: Prepare_ok (n, na, va) from majority: # } pick the largest one and the corresponding va, let v=va; Otherwise, choose your own V v = VA with Heighest NA; Accept request if accept_ok(n) from majority of acceptors: To accept Acceptor Acceptor state on each node (persistent): Prepare (n); prepare(n) : if n > np: Else: send prepare_reject accept(n, v) Handler: if n >= np: na = n va = v send accept_ok(n) else: send accept_rejectCopy the code

Intuitive understanding

Fault Tolerant Analysis^Explained

How exactly does Paxos guarantee consistency? Here’s an example.

3.1 Server Crash

If there are 2F + 12F + 12F +1 servers, a maximum of FFF server crashes can be tolerated. As a simple example, suppose a distributed system consists of five servers, two of which collapse at any given moment. 1. An Acceptor or Learner crashes. 2. The Leader crashes.

3.1.1. Acceptorcollapse

As shown in the picture below,S1forLeader, when it sends an Accept request,S4andS5Collapsed. butS1.S2.S3Still in the majority, so
$v$It can still be decided.

3.1.2. Leadercollapse

LearderCrashing is a little trickier. First, there is error detection to discover the leaderS1Hang up. Then, because there is no leader, there is a new election. As shown in figure,S1.S5I hung up, butS2.S2.S3Still in the majority.S2aprepareThe request,S3.S4Returns the most recently accepted
$v_1$.
$v_1$Once againS2Request acceptance. so
$v_1$Success was decided.

3.2 Network Partitioning

Another common mistake is network segmentation. As shown in the picture below,S1.S2withS3.S4.S5The communication between the two networks is disconnected and split into two sub-networks. In this miserable situation, the system can still reach consensus. Once segmentation occurs, it can be detected by error detection, such as timeout. And then the majority side would run for re-election, as shown here,S3Become the new leader. The system is up and running again. But that’s not the end of the problem. If network traffic returns to normal at any point, there will be two leaders in the distributed system! Can Paxos still guarantee consensus? Yes. because
$n_2>n_1$.S3 ~ S4Has promised not to accept
$n_2$Small proposal. So the old leaderS1The proposal of
$(n_1,v_1)$Will be rejected, andS3The proposal of
$(n_2,v’)$It will pass.

3.3 Message Lost

Since the network layer is unreliable, message loss and delay are unavoidable. The main way to deal with such errors is retransmission.

reference