3 ms·

So w.r.t. to (1), yeah, I totally get that. And I agree that is a hard problem to solve in the context of document editing (or more precisely, anything that con

So w.r.t. to (1), yeah, I totally get that. And I agree that is a hard problem to solve in the context of document editing (or more precisely, anything that contains a sequence). But for a graph, the logic is considerably simpler because a graph is just two sets. So if the system "loses" work that the client has done, it's only when some other client has deleted or changed something. So if two clients are editing the same graph and one drops a vertex and the other creates an edge that connects to that vertex, what is the right outcome in that circumstance? It seems to me like the edge gets deleted, and that this is a natural user conflict, no? (Regardless of how you order the operations in this case, the edge gets dropped.) W.r.t. to (2), yeah, sure, but if clients need to be able to remove things then you lose commutativity and you end up missing the requirements of the system itself. Or is there some other component of a CRDT system that's supposed to handle this? (My big picture takeaway from the OP paper was that it was specifically trying to handle the non-commutative operations.)

Karrot_Kream 9y ago
Yup! Removes are where a lot of these things get tricky. The typical strategy is as you say, removes take precedence over adds, so if one client adds vertices/edges onto a vertex that gets removed by another client, when the DAGs converge, the remove gets precedence and "drops" all edges/vertices attached. It seems like we're basically saying the same thing. Removes are also tricky because if you're just transmitting the remove operation itself, you have to ensure that updates appear to the client in order, or else removes and adds could conflict, causing inconsistent state.
- burntsushi 9y ago
  Yeah, in practice, each client maintains a persistent data structure, where each "mutation" is the application of a single operation. If a new operation comes in that occurs before other operations that have already been applied to the persistent data structure, then the client rewinds the structure to its state just before the new out-of-order operation, applies that operation, and then applies the rest of the operations that it already has. (I think of this as very similar to a `git rebase`.) But yeah, this might not work at all for sequences. And of course, there are other issues with respect to the memory requirements of the persistent data structure in the client. Some sort of compaction is probably necessary.

Karrot_Kream 9y ago

Yup! Removes are where a lot of these things get tricky. The typical strategy is as you say, removes take precedence over adds, so if one client adds vertices/edges onto a vertex that gets removed by another client, when the DAGs converge, the remove gets precedence and "drops" all edges/vertices attached. It seems like we're basically saying the same thing. Removes are also tricky because if you're just transmitting the remove operation itself, you have to ensure that updates appear to the client in order, or else removes and adds could conflict, causing inconsistent state.

burntsushi 9y ago
Yeah, in practice, each client maintains a persistent data structure, where each "mutation" is the application of a single operation. If a new operation comes in that occurs before other operations that have already been applied to the persistent data structure, then the client rewinds the structure to its state just before the new out-of-order operation, applies that operation, and then applies the rest of the operations that it already has. (I think of this as very similar to a `git rebase`.) But yeah, this might not work at all for sequences. And of course, there are other issues with respect to the memory requirements of the persistent data structure in the client. Some sort of compaction is probably necessary.