[hem777]

We don’t assume “reliable delivery” in AP or eventually consistent systems. We assume “once all messages have been delivered…”

So if you have all messages and the two properties above, a total order can be derived.

You’re correct to say that causal order != total order as such but with the use of correct primitives, like Lamport Causal Clocks, we can get a nice and clean linear order of events :)

[preseinger]

"correct primitives" do not by themselves provide a linear order of events

      a
     / \
    b   c
     \ /
      d

b and c are concurrent updates, how do you resolve d?

it's a trick question, you can't resolve d without information loss, unless you bring in additional knowledge from the application

you can resolve d with information loss by defining some heuristic for ordering concurrent updates, a.k.a. last-writer-wins, basically picking one of those updates deterministically

that gets you a total order, but it's cheating: whichever concurrent updates you don't choose are lost, and that violates consistency for any replica(s) that are based on that state

there is no free lunch

[hem777]

> "correct primitives" do not by themselves provide a linear order of events

Review the description of Lamport Causal Clock in the article. Note that it carries “additional info” (additional to the example diagram). This “additional info” is what establishes the structure needed for total order.

> whichever concurrent updates you don't choose are lost, and that violates consistency

They’re not lost! The concurrent updates not chosen are still part of the “list of operations”, but the update to the data/value itself may not be observable if the subsequent update (the update that was sorted to be first) updates the same data/value (eg. both operations update the same key in a key-value structure). If the two operations update different data/value, then both updated values are observable. This isn’t cheating, rather it works exactly as expected: it is eventually consistent.