Does paxos "ignore" the request for updating the value if it is not in sync with highest proposal number sent by acceptor?

Question

Title here could be misleading. I will try my best to explain my doubt through an example.

I am reading about paxos algorithm from wiki and other sources.

1) Imagine a situation where a client's request to update a value (X in below example) is processed. After one round of Paxos, a value Vb is chosen because Acceptors reply's to Proposers contain their previously accepted Proposal number and the corresponding value. In the case below, the three acceptors send (8,Va),(9,Vb),(7,Vc) to proposer which currently has (10,X). It picks up (9,Vb) since it is the highest proposal number it received and broadcast the value (10,Vb) to all acceptors for acceptance. So the initial value X for which this whole round of Paxos was processed never got updated. so is the client transaction of updating to X failed in this case?

What is the final state of Acceptors after this? Do they all have (10,Vb) as their highest accepted proposal number and values and thus be in sync?

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(10)
   |         |<---------X--X--X       |  |  Promise(10,{(8,Va),(9,Vb),(7,Vc)}
   |         X--------->|->|->|       |  |  Accept!(10,9,Vb)
   |         |<---------X--X--X------>|->|  Accepted(10,9,Vb)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

2) Now is a more complex case, where two proposals are made but at different time points when trying to reach consensus. That is imagine a situation where a client C1 in Region A is modifying some data X and has not yet reached consensus while client C2 in Region B is modifying same data X. Is one of Client's request rejected? please note C2 happens later than C1 but just that consensus has not reached yet. If ordering is followed, C1 request must be finished, consensus accepted and then C2 request be processed. From my understanding of this blog, in this case, C1 request value is chosen.

So Is C2 request abandoned? that might not be a good option.

Example (Copyright from this blog):

In this case, the v=8 is chosen finally, although request for V=5 is the most recent updated requested by client. why is it so? This could have serious impacts

Thanks for help and a happy new year!

Answer 1

To explain this I'm going to give some context--an interpretation of the OSI protocol stack:

+------------------------+
|100. Your Application   |
#========================#
|8. Some state machine   |
|   or key/value store   |
+------------------------+
|7. Transaction log      |
+------------------------+
|6. Paxos                |
+------------------------+
|5. Some framing protocol|
+------------------------+
|4. TCP                  |
+------------------------+
|...                     |
+------------------------+

Every serious implementation of paxos that I've seen uses a similar model (and I've seen many serious implementations). That is, Paxos is used to choose the next entry in a transaction log for a state-machine (becuase without a transaction log a database is just an expensive, slow, buggy cache). There is a different Paxos instance for every entry in the transaction log; they are completely independent; and if the designer of the system is exceptionally smart, the Paxos instances can even run in parallel.

Now on to your question.

Yes, X in your first example failed; it wasn't chosen. A failure should be returned to the upper layer. That may not necessarily mean a failure to the client ("your application" in the above model). The upper layers may decide to retry the value in a later entry in the transaction log; or they may just return a failure to the client.

In your second example, one of those requests MUST be rejected in the end--Paxos chooses at most ONE value. And once that value is chosen it stays chosen. As if Chuck Norris had chosen it.

But it looks like there is a little mis-understanding in that second example. It doesn't matter which request started first. Due to network latencies and the alignment of planets, the second request could muscle out the first.

Try it! With X,Y as values; P1,P2 as proposers; and A1,A2,A3 as acceptors:

1. P1 has X and sends Prepare(1)
2. A1 promises for 1 and returns Accepted(0,_)
3. A2 promises for 1 and returns Accepted(0,_)
4. A3 promises for 1 and returns Accepted(0,_)
5. P1 still has X and sends Accept(X,1)
6. A1 accepts(X,1)
7. P2 has Y and sends Prepare(2)
8. A2 promises for 2 and returns Accepted(1,_)
   • As you can see, A2 has switched to not accept any round less than 2
9. A2 rejects the Accept(X,1)
10. A3 promises for 2 and returns Accepted(1,_)
11. P2 still has Y and sends Accept(Y,2)
12. A2 accepts(Y,2)
13. A3 accepts(Y,2)
    • And having been accepted by the simple majority, Y has been chosen. No matter what any proposer does from here on out, the value of Y will always be chosen.

This is actually starts somewhat like the picture you have in your second example, but in this example the network favored the second proposer.