Geek Answers Handbook

Paxos value selection

I read about paxos on the wiki page and in the article (paxos made simple). However, I am still confused by some details:

  • In phase 1a, does the proposal he intends to select in the proposal for acceptors?

  • In phase 1b, the acceptor should return the value that it had previously taken, if any. What is the cost of life? IOW, when is it considered accepted and when is it being rewritten / deleted?

Some updates on lifetime. IIUC, after the first acceptance, the acceptor should always have a previously accepted value. How does he decide if he should return it in the next step (1b)? Or when does he decide to forget the cost?

Updates 2 to better discuss with @MichealDeardeuff:

I have an understanding for paxos:

Typically, in the paxos workflow, the acceptor should always have a previously accepted value. And, responding to a preparation request, it will send the value back in response to the promise. And the developer should check if the value is the same value as it was proposed in the last round. If this is not the case, then the initiator sends an accept request with the value returned by the acceptor. If so, the offer is then sent to send the Accept request with the value that it is intended to be sent in the current round.

Is understanding understood correctly?

If this is not true, could you explain why?

If this is correct, I am confused because the paxos protocol does not explicitly say this. He indicates only:

where v is the value of the sentence with the highest number among the answers, or any value if the answers do not report any offers.

However, as far as I know, the developer needs to check and see if the value returned by the acceptor matches the same proposal that was proposed in the last round. If this is the case, despite the fact that there is value with the offer with the highest number among the answers to the promise, then the developer can still choose any value that he wants, as if there were no values ​​returned by acceptors.

And it is for this reason that I want to see if there is any link to support understanding.

Thank you very much!

+4
source share
1 answer

In phase 1a, does the proposal he intends to select in the proposal for acceptors?

The supplier does not need to send the value that it intends to select before step 2a. See Also my answer to an earlier question.

In phase 1b, the acceptor should return the value that it had previously taken, if any. What is the cost of life? IOW, when is it considered accepted and when is it being rewritten / deleted?

From my answer to another question, "The acceptor should take all values, unless he promised to not accept it." . is, it must take any value with a round identifier greater than or equal to the rounded identifier in the last sent reply.

The reason it should take on any other value is because the creator can detect (as a result of phase 1) that another value should be chosen; or has been selected; he transfers this value to all acceptors. This discrepancy can occur when there are several proponents and / or during a network section.

Refresh to reply to a comment.

When an acceptor accepts a value, it is held at that value until it accepts a different value. (along with this it saves a round of value).

In Phase 1b, the Acceptor always sends its value, letting Proposer figure out what the actual value is. He never forgets his current meaning. Someday.

After receiving promises from acceptors, the offer has a beautiful view of the system. (Note: this is not necessarily a complete or updated view.)

Different acceptors may have assumed different meanings due to some disagreement with another proposal. Thus, the developer selects the value with the highest round identifier and sends this value to all acceptors. This is why acceptor values ​​can change.

The comments say this violates Paxos. Not this way.

But before I get an example, let me emphasize that it is much easier to think of Paxos with named phases and messages instead of 1a, 1b, 2a, 2b. I usually call the phases of the preparation phase and the adoption phase. With the message 1a as “Prepare,” 1b as “Promise,” “2a” as “Accept,” and “2b” as accepted.

Now let's look at a hypothetical example that people often give, and which, in their opinion, breaks Paxos. Suppose we have three receivers A1, A2 and A3. A1 and A2 have both the accepted value ABC in round 1, and A3 chose XYZ in round 2 (i.e. from another author of the proposal). We can see that A1 and A2 constitute the majority and that ABC is “chosen”.

Continuing this hypothetical example, the interlocutor sends Prepare (3) and receives back responses from A2 and A3, namely Promise (ABC @ 1) and Promise (XYZ @ 2). The pretext sees that XYZ has the highest round and sends it at the acceptance stage, overwriting ABC on other hosts. And viola, Paxos is broken, right?

No. The problem is the state of onset, which is impossible. Let me show you why.

Firstly, some suggestions that are key to Paxos working properly:

Proposal A : for A1 and A2, to have the value ABC @ 1, the developer should send Accept (ABC @ 1), which means that he should have received most promises in response to sending Preparation (1).

Proposal B : for A3, in order to be XYZ @ 2, the developer should send Accept (XYZ @ 2), which means that he should have received most promises in response to sending Prepare (2).

And now the proof:

Case 1: A1 and A2 already have the values ​​ABC @ 1. By virtue of Proposition B, for A3 to have the value XYZ @ 2, he had to get most promises from acceptors. Since the value of ABC belongs to most acceptors, at least one of them must send Promise (ABC @ 1). If 1 is the highest round identifier, the developer should select the value ABC and send Accept (ABC @ 2). But he did not, he sent Accept (XYZ @ 2). Contradiction.

Case 2: A3 already matters XYZ @ 2. (Remember that round 2 can come before round 1: the round identifier only increases monotonously for each author of the sentence.) According to sentence A, for A1 and A2 to have the value ABC @ 1, the developer should get most promises from acceptors. Similarly, according to Proposition B, for A3, in order to have it, most Promises also had to turn out. This means that the set {A1, A2}, which promised twice, must have at least one acceptor.

Case 2a: the acceptor sent Promise (1), then Promise (2). Then, when he received the Accept message (ABC @ 1), he had to reject it because he promised not to accept the value earlier than 2. But he did not reject it because he had the value ABC @ 1. Contradiction.

Case 2b: the acceptor sent Promise (2) first. Then, when he received the message “Prepare” (1), he should have rejected it because he had already promised a higher round. But this is clearly not because, on proposal A, it sent a promise (1). Contradiction.

Wow!

Hope this helps you.

Update 2 : Paxos pseudo-python implementation implemented here

from itertools import count from concurrent import futures class Acceptor(): def __init__(self): self.acceptedValue = None self.acceptedRound = None self.promisedRound = None def onPrepare(self, message): if self.promisedRound > message.round: send(message.source, new Nack()) self.promisedRound = message.round response = new Promise(round=self.acceptedRound, value=self.acceptedValue) send(message.source, response) def onAccept(self, message): if self.promisedRound > message.round: send(message.source, new Nack()) self.acceptedValue = message.value self.acceptedRound = message.round send(message.source, new Accepted()) class Proposer(): def __init__(self, selfId, quorum): self.quorum = quorum self.id = selfId # get a unique starting round, # assumes acceptors and proposers are on same hosts self.initialRound = sorted(quorum).index(selfId) def propose(self, value): "Propose a value to be chosen; returns actual value chosen" # round is always unique to a proposer # count(start, step) returns an infinite sequence for round in count(self.initialRound, len(self.quorum)) promises = self.prepare(round) if not promises: continue # interpret the prepare phase results, may be None selectedValue = max(promises, key=lambda p: p.round or -1) accepted = self.accept(round, selectedValue or value) if accepted: return value def prepare(self, round): "Drive the Prepare phase. returns the promises from the acceptors or None" message = new Prepare(round, source=self.id) responses = [] for acceptor in self.quorum: responses.append(send(acceptor, message))) # wait for the results promises = [] for response in futures.as_completed(responses): if response.exception(): continue # message died message = response.result() if not isinstance(message, Promise): # A nack message; abort the round. We may have got a majority, # but this speeds up the case when we didn't. return None promises.append(message) if (len(promises) > len(self.quorum) / 2: return promises # No majority of responses return None def accept(self, round, value): "Drive the Accept phase. returns True iff the value was accepted" message = new Accept(round, value) responses = [] for acceptor in self.quorum: responses.append(send(acceptor, message) # wait for the results accepts = 0 for response in futures.as_completed(responses): if response.exception(): continue # message died message = response.result() if not isinstance(message, Accepted): # A nack message; abort the round. We may have got a majority, # but this speeds up the case when we didn't. return False accepts = accepts + 1 if accepts > len(self.quorum) / 2: return True # No majority of responses return False

Refresh 3 To answer other questions from the comments.

... if this is the same value proposition sent in the last round, we want the initiator to ignore it (otherwise we will end the dead cycle, right?)

(Im assuming that “ignoring” the value means exiting the loop earlier.)

First, note that the loop ends when the requestor receives confirmation from most acceptors that the value is selected. So, if a developer does the next stage of preparation, you can be sure that he is competing with another offer or with some kind of network partition. Secondly, note that the preparation phase returns a value, even if only one acceptor accepted the value (this value cannot be accepted by the majority.)

If the Preparation phase leads to the value and its same value that he saw in the previous round, he should continue the Accept phase anyway for several reasons.

  • If the candidate leaves the cycle earlier, it is possible that another developer has failed. This may result in a value not being selected.
  • If he leaves the cycle earlier, it is reasonable that another developer, following the same algorithm, also left the cycle; again making it impossible to select a value.
  • If it so happened that the value was actually selected, it may be that not all nodes received the value (due to the network partition) or have a different value (because of this battle with a different sentence). Therefore, it is good to press the value for the nodes to ensure durability.

On the other hand, it is possible that Paxos goes into an endless cycle when there is competition between two or more developers and some failure. (This is true for any consensus algorithm, and was proved by Liskov et al. Before any consensus algorithm was discovered). Therefore, the theory says, but in practical systems it is easy to get around : on each subsequent round, pause for a random period of time so that the other challenger can win the race. Of course, it is still possible to have an endless cycle, but it is unlikely to ever happen in the life of the universe.

Do you have a link to argument support?

I speak mainly from my own experience and experience. I am on a team that develops and maintains a system built with Paxos. I have also done extensive research on this.

Here are some good related articles:

Update 4 . Responses to updates in the question.

Typically, in the paxos workflow, the acceptor should always have a previously accepted value. And, responding to a preparation request, it will send the value back in response to the promise. And the developer should check if the value is the same value as it was proposed in the last round. If this is not the case, then the initiator sends an accept accept request with the value returned by the acceptor.

Okay bye. But the developer does not need to maintain state between rounds. We will soon find out why.

If it is [the same value], the proposal then proceeds to send the Accept request with the value that it is intended to be sent in the current round.

If any value is returned by the acceptor, then at the acceptance stage it is necessary to use the one with the highest round identifier. If no value is returned by the acceptor, then any value can be used: my logic assumes that it will be the value that the client passed to the offeror.

Compare this to Paxos Made Simple (p. 6):

... where v is the value of the offer with the highest number among the answers or any value if the answers do not report any offers.

(A kind of harsh terminology switches between documents. Here Lamport uses terms with numbered sentences, elsewhere it uses the term round-id. There is one and the same.)

Suppose that the creator starts the preparation phase and sees this state among the acceptors.

  A1 A2 A3 promise: 3 ? 4 value@round : x@3 ? y@4

where is the actual condition

  A1 A2 A3 promise: 3 4 4 value@round : x@3 y@4 y@4

Now suppose he completed the previous round with a value of y. IF is allowed to select any value at this point, it can force this state:

  A1 A2 A3 value@round : z@5 z@5 z@5

This overwrites the selected value that violates the consensus consistency property (Viz, You can select no more than one value. ).

If you want this behavior, you cannot use the consensus protocol as is. You can use protocols such as ABD or another round register . Or you can think of Paxos as the choice of transition in the final machine. In other words, every time you want to change a variable, you run a new Paxos algorithm to select a transition. This is what my system does (and I dare say that most Paxos practical systems).

Note. The ABD and round-based registers operate similarly to Paxos, but a little easier, because they do not have to guarantee the specified consistency property (after the selection, always selected). But the Paxos-based state machine allows CAS operations for variables.

+9
source

More articles:


All Articles