3 ms·

> "having the instances always process [ops] in the same order" is basically not possible in any real-world network By having 1) causal order (eg. using what t

by hem777 4y ago

> "having the instances always process [ops] in the same order" is basically not possible in any real-world network By having 1) causal order (eg. using what the article refers to as Lamport Causal Clock) and 2) a deterministic sorting function to sort ops that happened concurrently (from the perspective of causal order), we can derive total order. It’s absolutely possible and used. And with those two properties, almost any data structure can be turned into a (op-based) CRDT. That is to say, thoughtlede has it correct in their comments above.

preseinger 4y ago
this just isn't true total order is property that can only exist over a well-defined set of messages without reliable delivery (and stable network tomography) there is no way to establish a well-defined set of messages causal order (via lamport clocks or otherwise) just doesn't establish total order (by itself)
- hem777 4y ago
  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 4y ago
    "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 4y ago
      > "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.
      - preseinger 4y ago
        we are only talking about updates to a specific value here, obviously updates to independent values are trivial to resolve it's possible to construct a CRDT such that concurrent updates are merged without data loss to a single "list of operations" maintained in the object, but that's not true in general resolving conflicts with the lww strategy, or variants of that strategy that order concurrent events by e.g. node ID, are indeed eventually consistent at the highest level, but they provide no meaningful consistency guarantees to users, because they allows "committed" writes to be lost
        hem777 4y ago
        > that's not true in general Can you elaborate what do you mean by this? I was arguing that it’s possible as the original argument was “this is not possible in a real system and is only theoretical”. > provide no meaningful consistency guarantees to users, because they allows "committed" writes to be lost If I set the (shared) value to green and you set it to blue, what is the expected observed value? What if you set it to green and I set it blue, what is the observed value? More importantly, what is the consistency that was lost?
        4y ago

by hem777 4y ago

preseinger 4y ago

this just isn't true total order is property that can only exist over a well-defined set of messages without reliable delivery (and stable network tomography) there is no way to establish a well-defined set of messages causal order (via lamport clocks or otherwise) just doesn't establish total order (by itself)

hem777 4y ago
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 4y ago
  "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 4y ago
    > "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.
    - preseinger 4y ago
      we are only talking about updates to a specific value here, obviously updates to independent values are trivial to resolve it's possible to construct a CRDT such that concurrent updates are merged without data loss to a single "list of operations" maintained in the object, but that's not true in general resolving conflicts with the lww strategy, or variants of that strategy that order concurrent events by e.g. node ID, are indeed eventually consistent at the highest level, but they provide no meaningful consistency guarantees to users, because they allows "committed" writes to be lost
      - hem777 4y ago
        > that's not true in general Can you elaborate what do you mean by this? I was arguing that it’s possible as the original argument was “this is not possible in a real system and is only theoretical”. > provide no meaningful consistency guarantees to users, because they allows "committed" writes to be lost If I set the (shared) value to green and you set it to blue, what is the expected observed value? What if you set it to green and I set it blue, what is the observed value? More importantly, what is the consistency that was lost?
        4y ago