paxos - could someone explain Accept message with example

Question

I read this post on Paxos paxos value choice but still I am not clear. Assume we run the Paxos for first time and Proposer sends the Prepare and the Acceptors reply with (null, null) since they have not learned any value and so Proposer agrees upon its own value and sends it to the acceptors which they accept. The thing which is confusing me is when a Proposer has received the Promise-acks and needs to send an Accept message:

If any Acceptors had previously accepted any proposal, then they'll have sent their values to the Proposer, who now must set the value of its proposal to the value associated with the highest proposal number reported by the Acceptors. (from Wikipedia)

I don't understand this—what is the significance of selecting the "value associated with the highest proposal number reported by the Acceptors?" Can some body explain this with an example please?

Answer 1

In many distributed protocols and lock-free/wait-free algorithms an actor will finish up the work that another actor may not have finished. The proposers in Paxos will finish up the work of the other proposers whenever possible. (It's not all about muscling out the other proposers.) This is really important if the original proposer or some of the acceptors become unavailable during the course of the algorithm.

For example, the original Proposer (Paul) sends out his Prepares and Accepts, but dies before sending the accept to one of the acceptors (Art). A majority of the acceptors have accepted the value (A), so the value is chosen, but the entire system may be in the dark about it. Along comes another proposer, Peggy. She sends out her own proposal and learns from Adam that the value A has been accepted by somebody. Note, it may or may not have been a majority. To be on the safe side, she sends A back out, and now Art learns the value.

Paul            Alice Adam Art            Peggy
 |-propose(1)--->|---->|--->|
 |<----ack(_,_)--|-----|----|
 |-accept(A,1)-->|---->|    X               +
 X               |<----|<---|<---propose(2)-|
                 X     |------ack(A,1)----->|
                            |-ack(_,_)----->|
                 |<----|<---|<--accept(A,2)-|
                 |-----|----|-ack---------->|

You can see that at least two things happened here: In the prepare phase, Peggy learned the accepted value; in the accept phase she propagated the chosen value to the rest of the Acceptors.

It needn't have been the case that the value was accepted by a majority of acceptors, as in the example above. But Peggy only has to wait for a majority of prepare-acks before getting sending out her accept messages. That's because a simple majority of accepted answers will always contain the chosen value.

(Note, if Peggy did not send out the value A, she would have changed the chosen answer which violates the consensus invariant.)

Let's take another example where multiple values are returned by a prepare-ack: (A,1) and (B,2). We can make some deductions from this scenario.

1. The presence of (B,2) means a majority of acceptors have ack'd a prepare(2) message, thus
2. It is unlikely that A has been chosen (but not impossible) because a majority of acceptors will reject an accept(A,1) message.
3. The presence of (B,2) also means it is possible that B has been chosen by a majority of acceptors. The proposer won't know for sure until it receives the accept-acks.

---

Update: Answering a few questions from the comments.

What roll does the client play in all this?

It depends on the application. The Paxos application I maintain is driven by two types of external events: time and client write requests. The client requests writes into a database; the server uses Paxos to both replicate and agree on the write; and then the result is sent back to the client. The client in my application doesn't know about Paxos at all and does not participate in the protocol.

In other applications, the client could take on the role of being the proposer.

Why doesn't Peggy use her own value after the Prepare phase?

First, note that Peggy only waited for a simple majority of acceptors [ceil( N/2 )] to respond. That means that the result of ceil( N/2 ) - 1 acceptors is unknown to Peggy. That number is one less than a simple majority.

If Peggy receives back a value from the Prepare phase, she must assume that the rest of the hosts also have that value. This would pass the threshold of a simple majority, meaning that value could have been chosen by a majority. If Peggy were to use her own value should could (and sometimes would) violate the consensus invariant that once a value is chosen, that same value is always chosen.

Why does Peggy use the value associated with the highest value returned by the Prepare phase?

The answer to this is right above the update, where she considers multiple values returned by the Prepare phase. Basically, she assumes the highest returned value has been accepted by a majority of acceptors; and that the majority of acceptors will reject any value with a lower round-id (which they will).