[kiitos]

Give up on the idea of "the timestamp" of an event. There is no such thing. Clocks are unreliable, and even if every clock in a system is perfectly in-sync (via atomic transponders or whatever) they're still subject to speed-of-light discrepancies that make it impossible to define "the time" of any event.

Two nodes separated by 10000km require ~33ms to send information in one direction, and ~66ms to do a roundtrip. Send X=1 to node=A from a client that's 5ms away from A at client-local time T1, and then send X=2 to node=B from a client that's 4ms away from B at client-local time T1-1ms -- when were these values sent, and what is the value of X? There is no answer, X is both 1 and 2, depending on when and who you ask.

You can define a leader node C, which receives updates from child nodes A and B, and that leader node can serialize updates in a way that produces a single linearizable sequence of updates, sure. But then that sequence of updates as defined by C needs to be propagated to child nodes A and B, which takes (let's say) 66ms round-trip minimum. So when your client sends X=1 to node=A, it has to wait for at least 66ms before it can make a correct read from that same node -- X may actually be 2!

Logical ordering of events in a distributed system is a solved problem. The solution is vector clocks (or something like them).

[toast0]

> Logical ordering of events in a distributed system is a solved problem. The solution is vector clocks (or something like them).

Vector clocks don't solve this problem, as they only provide a partial ordering. When multiple messages are in flight in the same 'simultaneity window', different observers may receive them in different orders and vector clocks can't determine a consistent order of those events.

Vector clocks could be used determine the order is inconsistent. But what do you do with that information? You might likely have follow on events where A and B are unordered, and A1 was sent only seeing A, B1 sent only seeing B, and C was sent seeing A and B without seeing A1 and B1. It only gets more complex from there.

I'm not a UX person, but I can't imagine how to show this to users without causing massive confusion and information overload. There's a very small set of people that have studied distributed communication that would get this. And I haven't seen any UI that shows similar information in a coherent way... maybe git graphs, but I don't see how you make that fit on a phone screen where you're having a group chat.

Maybe just some indicator that says other people may see these messages in a different order, but then if it's not an immediately obvious signal, it's not really going to help users understand.

[kiitos]

> When multiple messages are in flight in the same 'simultaneity window', different observers may receive them in different orders and vector clocks can't determine a consistent order of those events.

That's right! Vector clocks only provide partial order. But partial order is the only actual truth in any distributed system. Total order is a fiction, which only exists in the context of a specific node, based on that specific node's experience of reality (message receipt).

In any non-trivial distributed system, there is no consistent (total) order of events, at least not without a consensus protocol. There are lots of ways to hack a (fake) total order, and many of those approaches are enormously successful nearly all of the time. But, still, you know.

[toast0]

I don't understand why you seem to agree with me but also said

> Logical ordering of events in a distributed system is a solved problem. The solution is vector clocks (or something like them).

A partial order solves the problem when messages are not simultaneous and so the partial order provides a total order. That there is in fact no total ordering of simultaneous messages doesn't solve the problem that users would like to have messages arrive in a consistent order without delay. This is unsolved, because it's unsolvable, therefore vector clocks aren't the solution.

[kiitos]

Vector clocks provide a deterministic partial order, but partial order doesn't provide any kind of total order. That's true, yes.

But (as I'm sure you're aware) there is no single deterministic total order of events in a distributed system. The system can assert some specific total order, based on some specific criteria -- say, LWW based on node identity -- but that's system-specific and arbitrary.

That "users would like to have messages arrive in a consistent order without delay" is a nice and valid expectation, but is literally impossible, in the general case. Vector clocks solve a lower-level problem; nothing can solve the higher-level problem.

(Again, as I'm sure you're aware.)