How does clients observe different replicas and stale data even if the replicas include same set of updates?

Question

I am studying about gossip architecture. This is gossip architecture-:

Gossip architecture provides 2 guarentees-:

1)Each client gets consistent service over time(meaning even if clients use different RMs, the returned data reflects the updates seen by client as of now)

2. Relaxed consistency between replicas-: All RMs eventually receive all updates and apply updates with ordering guarentee.

But here is the confusion.

It also says-:

Two clients may observe different replicas even though replicas include same set of updates, ana client may observe stale data.

How can 2 clients observe different replicas when replicas include same set of updates and ordering is guarenteed?

As per my inituition, it is probably because since the consistency is relaxed so at that moment, all replicas don't have same set of updates.

And may be that's why clients observe stale data. Am I correct?

Answer 1

this is not an definite answer, but more like an educated guess, so please be sceptical

this link has some thoughts about partial ordering and what vector clocks can actually do: https://scattered-thoughts.net/writing/causal-ordering/.

From what I see - partial ordering is ordering that does not (cannot?) order all events, just some. A replica can have several updates which are not ordered, i.e., it cannot say in which order they arrived.

The clients (or FEs) communicate their last timestamp prev, e.g., prev_1 and prev_2. Some updates on the replica can potentially be ordered with respect to each prev, i.e., some updates are newer than prev_1 and some than prev_2. But you cannot say whether prev_1 is newer than prev_2 or the respective updates are newer than each other. Thus when two clients provide two different values of prev, replicas may return different updates.

Example: Let's say variable x had a value x_0 at some time t_0 (in vector clock values) on all replicas. Client 1 connects to replica 1 and updates x to value x_i. Around the same (human) time[1] client 2 connects to replica 2 and updates x to x_j. Each event gets assigned a timestamp in update id. Let's call them t_i and t_j. Then client 3 changes x_i to x_ii, which is assigned a timestamp t_ii, while client 4 changes x_j to x_jj at timestamp t_jj.

Eventually, all updates reach all replicas. Each replica can say that t_jj happened after t_j and t_j happened after t_0, i.e., x_jj is newer than x_j which is newer than x_0. The replica can say that t_ii > t_i > t_0, i.e., x_ii is newer than x_i. But it can't say whether x_ii is newer than x_jj or vice versa.

Now clients 1 and 2 go to the same replica and request a value. Client 1 provides his last timestamp t_i and client 2 provides his last timestamp t_j. Then replica should give client 1 a value x_ii, since it is newer than t_i and client 2 a value x_jj, since it is newer than t_j.

I think the same logic happens if there are clients 4 and 5 who asked two different replicas, each one knew only about x_i/x_j respectively. Once all updates reach all replicas these 2 clients will also get different values based on timestamps they provide.

[1] read as, the updates about x_1 did not reach other replica