6 ms·

> CRDTs don't _ensure_ ops are commutative (and associative, and idempotent) but rather they _require_ that ops are commutative (and associative, and idempotent

> CRDTs don't _ensure_ ops are commutative (and associative, and idempotent) but rather they _require_ that ops are commutative (and associative, and idempotent) I disagree. You can create a CRDT flavor of data structure whose ops are not commutative. For example, a Set's add and delete operations. These are not commutative. You cannot switch the order of the ops for meaningfully processing them. However, you can create a CRDT Set. You do that by adding metadata to the ops, and having the instances always process them in the only order that makes sense even if such instances receive the ops in a different order. In that sense, you are "ensuring" ops are behaving like they are commutative and not "requiring" them to be so. > it's definitely not the case that any data structure is a CRDT I could have worded my statement better. I meant any data structure that has the aforementioned duality property is a CRDT. Not that any data structure unconditionally can be translated into a CRDT. > an important "eureka" observation about CRDTs is that the op-based model is theoretical, I do not understand your statement. Perhaps you could elaborate. My understanding is that a CRDT is op-based or state-based depending on what is "communicated" between the instances. If ops are communicated, then it is op-based CRDT, whereas if states (or delta-states) are communicated, then it is state-based. At least in that sense, op-based model is NOT theoretical. Perhaps you have a different point in mind that I fail to observe.

preseinger 4y ago
> I disagree. You can create a CRDT flavor of data structure whose ops are not commutative. For example, a Set's add and delete operations. These are not commutative. You cannot switch the order of the ops for meaningfully processing them. However, you can create a CRDT Set. set add (union) is commutative, set delete is not. so a set with only the add (union) operation is a CRDT, but a set that supports both add and delete is not a CRDT, at least not without very specific caveats. you can create an add-only CRDT set, or an add-remove CRDT set, or a variety of other CRDT sets that support specific operations with specific caveats. but you can't create a CRDT set that is a fully-fledged set, with all the operations that sets generally provide. > You do that by adding metadata to the ops, and having the instances always process them in the only order that makes sense even if such instances receive the ops in a different order. so this is the crux of the issue, I think -- "having the instances always process [ops] in the same order" is basically not possible in any real-world network first, because it's not possible to decide what the "correct" set of ops actually is, nodes are always subject to partitions, faults, etc. which prevent reliable dissemination of knowledge, and plus all the stuff about light cones and etc. second, because "the same order" implies a specific total ordering of events is unknowable (see prior comments) > you are "ensuring" ops are behaving like they are commutative and not "requiring" them to be so converting a non-commutative operation to a commutative operation in a distributed system requires reliable delivery, which no network provides the whole point of CRDTs is that they give you a formally strong version of eventual consistency that holds even in the face of (unavoidably) unreliable delivery > My understanding is that a CRDT is op-based or state-based depending on what is "communicated" between the instances. If ops are communicated, then it is op-based CRDT, whereas if states (or delta-states) are communicated, then it is state-based. this is true in the abstract, but the issue is that "what is communicated" is not a given, it's subject to the choices you make when you encounter a network fault -- or in the CAP model, a partition CRDTs are tools for eventually consistent (AP) systems, which means that you have to keep making forward progress if there are partitions, which means that message delivery between nodes is not reliable, it can always fail for state-based CRDTs if you fail to deliver a message it's fine, the information in that message is not lost forever, it will be included in the next message, and (if the partition is eventually healed) the ultimate state will converge. this is also true for delta states but for op-based CRDTs if you fail to deliver a message it's not fine, the information in that message is lost forever, it won't be included in the next message, and (even if the partition is eventually healed) the ultimate state will not converge
- 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
preseinger 3y ago
> > CRDTs don't _ensure_ ops are commutative (and associative, and idempotent) but rather they _require_ that ops are commutative (and associative, and idempotent) > I disagree. You can create a CRDT flavor of data structure whose ops are not commutative i think it's important to reiterate (for other third-party readers) that this is factually incorrect a data structure with operations that are not commutative (or associative or idempotent) is not a (state-based) crdt by definition

preseinger 4y ago

> I disagree. You can create a CRDT flavor of data structure whose ops are not commutative. For example, a Set's add and delete operations. These are not commutative. You cannot switch the order of the ops for meaningfully processing them. However, you can create a CRDT Set. set add (union) is commutative, set delete is not. so a set with only the add (union) operation is a CRDT, but a set that supports both add and delete is not a CRDT, at least not without very specific caveats. you can create an add-only CRDT set, or an add-remove CRDT set, or a variety of other CRDT sets that support specific operations with specific caveats. but you can't create a CRDT set that is a fully-fledged set, with all the operations that sets generally provide. > You do that by adding metadata to the ops, and having the instances always process them in the only order that makes sense even if such instances receive the ops in a different order. so this is the crux of the issue, I think -- "having the instances always process [ops] in the same order" is basically not possible in any real-world network first, because it's not possible to decide what the "correct" set of ops actually is, nodes are always subject to partitions, faults, etc. which prevent reliable dissemination of knowledge, and plus all the stuff about light cones and etc. second, because "the same order" implies a specific total ordering of events is unknowable (see prior comments) > you are "ensuring" ops are behaving like they are commutative and not "requiring" them to be so converting a non-commutative operation to a commutative operation in a distributed system requires reliable delivery, which no network provides the whole point of CRDTs is that they give you a formally strong version of eventual consistency that holds even in the face of (unavoidably) unreliable delivery > My understanding is that a CRDT is op-based or state-based depending on what is "communicated" between the instances. If ops are communicated, then it is op-based CRDT, whereas if states (or delta-states) are communicated, then it is state-based. this is true in the abstract, but the issue is that "what is communicated" is not a given, it's subject to the choices you make when you encounter a network fault -- or in the CAP model, a partition CRDTs are tools for eventually consistent (AP) systems, which means that you have to keep making forward progress if there are partitions, which means that message delivery between nodes is not reliable, it can always fail for state-based CRDTs if you fail to deliver a message it's fine, the information in that message is not lost forever, it will be included in the next message, and (if the partition is eventually healed) the ultimate state will converge. this is also true for delta states but for op-based CRDTs if you fail to deliver a message it's not fine, the information in that message is lost forever, it won't be included in the next message, and (even if the partition is eventually healed) the ultimate state will not converge

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

preseinger 3y ago

> > CRDTs don't _ensure_ ops are commutative (and associative, and idempotent) but rather they _require_ that ops are commutative (and associative, and idempotent) > I disagree. You can create a CRDT flavor of data structure whose ops are not commutative i think it's important to reiterate (for other third-party readers) that this is factually incorrect a data structure with operations that are not commutative (or associative or idempotent) is not a (state-based) crdt by definition