Is Paxos Strongly Consistent?

Question

Consider a distributed system with 3 nodes- n1, n2, n3. There is a shared data, x, among the nodes. Paxos is running on the nodes. In the beginning, x is equal to 4.

A client sends an update request to n1 to change the value of x to 5. n1 and n2 reach consensus on the new value by running Paxos but some link failures occur for n3, so n3 does not have the newest value of x.

We know that Paxos provide Strong consistency. In the other hand, if a client sends a read request to n1 and also another read request to n3, the returned values are not the same (one of them is 5 but the other one is 4). Therefore, after running Paxos, the system is not strongly consistent.

My question is: How we can resolve this contradiction? Did I misunderstand something?

Answer 1

In multi-paxos, peers can lag behind as you noticed. If you read the values from a quorum though you're guaranteed to see the most recent value, the trick is figuring out which one that is. Not all applications need this but if yours does, a very simple augmentation is sufficient. Just use a tuple instead of the raw value where the first item is an update counter and the second is the raw value. Each time a peer tries to update the value, it also updates the counter. So when you read from a quorum, the tuple with the highest update counter is guaranteed to be the most recent value.