This is the 27th day of my participation in the August More Text Challenge

In the PAXOS algorithm, there are three roles:

  • Proposer
  • Acceptor
  • Learner

In a concrete implementation, a process may perform multiple roles simultaneously. For example, a process may be both Proposer and Acceptor and Learner.

Another important concept is a Proposal. The final value to be agreed upon is in the proposal.

Problem description

Suppose you have a set of processes that can produce values (values are in the proposal). A consistency algorithm needs to ensure that only one of the multiple values proposed is selected. If no value is proposed, no value should be selected. If a value is selected, all processes should be able to learn to the selected value. For the consistency algorithm, the security requirements are as follows:

  1. Only the proposed value can be selected;
  2. Only one value is selected;
  3. If a process task has a value selected, the value must be the one that was actually selected.

The goal of Paxos is to ensure that eventually a value is selected, and that when a value is selected, the process eventually retrieves the selected value.

Derivation process

Simplest solution – only one Acceptor

If there is only one Acceptor, the proposal is selected as long as the Acceptor accepts the first proposal it receives. The value in the proposal is the selected value. This ensures that only one value is selected. However, if this unique Acceptor fails, the entire system will not work. Therefore, multiple acceptors are required.

If there are more than proposers and acceptors, how do you guarantee that you select a value?

Let’s start looking for a solution.

If we want even if only one Proposer presents a value, that value is eventually selected. Then, we get the following constraint:

P1: An Acceptor must accept the first proposal it receives.

But this raises a new problem if each Proposer presents a different value to a different Acceptor. According to P1, if acceptors accept values separately, different values will be selected, resulting in inconsistencies.

This is because the value of a proposal is selected whenever an Acceptor accepts it. Therefore, we need to add a rule:

A proposal must be accepted by more than half of acceptors.

This rule implies that an Acceptor must be able to accept more than one proposal! ** Otherwise, no value may be selected. Like the picture above. Value1, value2, and value3 are not selected because they are accepted by only one Acceptor.

At this point, our ** proposal =value scheme needs to be redesigned, and each proposal needs to be given a proposal number, indicating the order in which proposals are proposed. Time proposal =[no., value]**.

Although we allow multiple proposals to be selected, we must ensure that all selected proposals have the same value, otherwise inconsistencies will occur again. Therefore, in combination with the proposal number, the following provisions can be given:

P2: If a proposal with value=v is selected, then all proposals with higher numbers must also be selected with value v.

A proposal can only be selected if an Acceptor accepts it, so we can rewrite the P2 constraint P2a to the proposal accepted by an Acceptor.

P2a: If a proposal with value=v is selected, all Acceptor proposals with higher numbers must also have value v.

However, because communication is asynchronous, a proposal may be selected before one of the acceptors has received the proposal.

As shown in the figure above, when Acceptor1 has not received any proposals, the other four acceptors have accepted proposals from Proposer 2 [M1,V1], at which point Proposer1 produces a proposal [M2,V2] with a higher number and a different value. Send to Acceptor1. According to P1 (an Acceptor must accept the first proposal it receives), an Acceptor needs to accept the proposal. However, this contradicts P2a, so to satisfy both P1 and P2a, P2a needs to be strengthened as follows:

P2b: If a proposal is selected, then any subsequent proposals with a higher numbered numbered must also have a value of V.

Since a proposal must be submitted by an Acceptor before it is approved, P2b contains P2a and, by extension, P2.

If a Proposer with a value of V is selected, how do you ensure that the proposals with a higher number are numbered with a value of V? (Please refer to the mathematical induction proof in distributed Consistency Principle and Practice from PAXOS to ZooKeeper for details.)

As long as it satisfies P2c:

P2c: For any M and V, if the proposal [M, V] is proposed, there exists a set S consisting of more than half of acceptors that satisfies either of the following two conditions:

  • No Acceptor in S has accepted a proposal numbered less than M.
  • The value of the proposal with the largest number accepted by an Acceptor in S is v.

A Proposer generates a proposal

To satisfy P2c, there is an important idea: if a Proposer produces a proposal, it should learn a value that has been selected or is likely to be selected, and then use that value as the value of its proposal. If no value is selected, the Proposer can determine the value itself. That’s how we reach an agreement. This learning phase is achieved through a Prepare request.

Thus, we obtained the following proposal generation algorithm:

  1. A Proposer selects a new proposal number, M, and then sends a request to a set of acceptors (more than half) asking each of those acceptors to respond with the following:

    1. To this Proposer promises not to accept any proposal numbered less than M.
    2. If an Acceptor has accepted a proposal, it responds to a Proposer with the largest number less than M that it has accepted.

    We call this request the Prepare request for the proposal numbered M.

  2. If the Proposer receives a response from more than half of the acceptors, it generates a proposal numbered M with value V. Where V is the value of the proposal with the largest number among the responses. If there are no proposals in any of the responses, then V can have a numbered proposal of its own.

    When a Proposer generates a proposal, it sends it to more than half of the acceptors it expects to accept it. We call the change request an Accept request.

Acceptor accepts the proposal

An Acceptor may receive two requests from a Proposer, Prepare and Accept, with the following conditions for a response.

  • Prepare request: Acceptors can respond to a Prepare request at any time.
  • Accept requests: You can respond to any Accept request without violating Accept’s existing commitments.

The constraints on Acceptor logic processing can be defined as follows:

P1a: An Acceptor can accept a Prepare request numbered M as long as it has not responded to any Prepare request numbered greater than M.

If an Acceptor receives a Prepare request with the number M, it has previously responded to a Prepare request with the number greater than M. According to P1a, this Acceptor cannot accept a proposal numbered M. Therefore, the Acceptor can ignore the Prepare request with number M. Currently, a Proposer can also respond with an error to let it know as early as possible that its proposal will not be accepted.

Therefore, an Acceptor simply needs to remember:

  1. The proposal with the largest number accepted.
  2. The maximum number of requests that have been responded to.

Algorithm statement

If a Proposer and Acceptor process a proposal with a proposal, the following two phases are obtained:

Phase 1:

  1. Proposer selects a proposal number M and sends a Prepare request numbered N to more than half of the acceptors.
  2. If an Acceptor receives a Prepare request numbered M greater than any Prepare request it has responded to, it sends back to the Proposer as a response the highest-numbered proposal (if any) it has accepted. The Acceptor also promises not to accept any proposal numbered less than M.

Stage 2:

  1. If a Proposer receives more than half of its acceptors in response to a Prepare request numbered M, it sends an Accept request to more than half of those acceptors. Note: V is the value of the highest-numbered proposal in the response received. If the response does not contain any proposals, then V is decided by the Proposer itself.
  2. If an Acceptor receives an Accept request for a proposal numbered M, it can Accept the proposal as long as the Acceptor has not yet responded to a Prepare request numbered greater than M.

Learner gets the proposal

A principal Proposer is selected to ensure that the algorithm is active

To keep the algorithm active and avoid this loop, a master Proposer must be selected and only that master Proposer can propose a proposal. A Proposer with a higher numbered proposal is approved if it communicates with a majority of acceptors properly.

The resources

  • Paxos Made Simple
  • Paxos Made Simple translation
  • Distributed Consistency Algorithm from Paxos to ZooKeeper