3 ms·

This spawned an idea, which I feel a need to post. It seems the hard part about CRDT is choosing the correct commutative function, as merging two operations in

This spawned an idea, which I feel a need to post. It seems the hard part about CRDT is choosing the correct commutative function, as merging two operations in line with user intent is non-trivial. Would it be possible to use a combination of superposition (Please correct me if this word is wrong) and pruning to derive user intent? The idea being that instead of combine being (A, A): A (A commutative semigroup), couldn’t we represent the operation as (A, A): Set[A] and have a way of showing the user set results in a way that their next operation shows us the “correct” interpretation. He’s doing this implicitly with the file tree example, wherein operations that don’t create trees usually defy user expectations (Symlinks aside), so he decides to prune those choices from the result Set[A] before introducing a heuristic to further prune the set. There’s still an issue of users having opposite intent, but at that point it just seems like we need to introduce “Set pruning” or “Superposition collapse” operations as a user-level primitive and then rely on recursion to resolve the possible nesting of these result sets. Does this riff with anyone / does anyone have further thoughts on this formulation?

benrbray 6y ago
This sounds similar to the concept of a "multi-value register" [1] I've seen in a few places while reading about CRDTs the last couple days. Is that what you're looking for? The idea is that each process maintains a vector clock with the latest timestamp from all other processes, and we don't delete values until one version can be verified to be "later" than all the others. [1] Section 3.2ish of https://hal.inria.fr/inria-00555588/document https://hal.inria.fr/inria-00555588/document
- alextheparrot 6y ago
  This was 100% the path I think I was traveling (Thank you for the link). I had a hard time grocking the complete specification from the paper, but the README of this repository that implements CRDTs in that frame was helpful [1]. The core part is separating the "merge" from the "resolve" state. Merging state can be done in a variety of ways, so in the default formulation there seems to be a focus on making the "merge" operation also "resolve" to only one value, when really there could be multiple formally valid merges that the client may desire (Which is part of the difficulty that the video notes as he proposes a variety of possible file system mutations for a set of two uncoordinated operations). The cleanest clarification of my thought process is similar to the following: Given the operation Merge(4, 2), I could propose that there are two valid ways to perform this merge, addition and multiplication. This means the result would be either 6 or 8. The act of returning a single value (6 or 8) changes that proposal into a statement, though, which is the "resolve". One subversion of this restriction is to return a set of all possible results for the operations we think are valid, so {6, 8}. At this point, the user can say (Either explicitly or implicitly) "I actually want 6" and we resolve it to the single value of {6}. There are also special cases like Merge(2, 2), where this whole situation is especially ergonomic because the merge operations are equivalent. There are problems, of course, with this approach. One issue is the need to categorize all possible operations the user may think are valid for Merge(4,2). If the user intended to do division, the result set proposed above will not include the state that they would expect. Still, this seems more general now, as we just need to gather the set of operations that the user may think are valid instead of assuming which one is valid. There's also a ranking problem that then exists at the UX level, as we need to find a way to cleanly propose this set of alternatives. Another issue is, of course, exists if both users propose conflicting resolutions (Actor1 says "I want multiplication" and Actor2 says "I want addition"). This is the issue with decoupling the "merge" and "resolve" steps, as now we may cause a fork in the model which causes a fundamental divergence of the collaborator's data. [1] https://github.com/rust-crdt/rust-crdt https://github.com/rust-crdt/rust-crdt
- macawfish 6y ago
  Oh wow! I've been studying CRDTs for a year but never understood what a multi-value register would be used for, so I'd ignored it... But I get it now. Also because it sounded like a concept from the 70s or something.
rst 6y ago
This might be a reasonable UX in some cases -- but it seems to assume that whichever user chooses an alternative also gets to broadcast that choice and have it immediately binding on all the others -- which is incompatible with some use cases for CRDTs. Failing that, you've just kicked the can down the road. Consider two users A and B who make conflicting edits, and so wind up being presented with one of these choices. If they choose different options, and then make further edits, what do they see of each others' subsequent edits, and how do you explain the whole branched history to user C, who was out to lunch while this happened?
- alextheparrot 6y ago
  It does kick it down the road, but it also doesn’t make it unresolvable — one issue the video seemed to articulate is that the writer of the “merge” function needs to make a choice for the user about what “combine” looks like which is often the root of weird UX. The idea here was “Maybe we can not make a choice, but still expose valid results to the user so that they can make a choice”. It definitely isn’t fully fleshed our, though

benrbray 6y ago

This sounds similar to the concept of a "multi-value register" [1] I've seen in a few places while reading about CRDTs the last couple days. Is that what you're looking for? The idea is that each process maintains a vector clock with the latest timestamp from all other processes, and we don't delete values until one version can be verified to be "later" than all the others. [1] Section 3.2ish of https://hal.inria.fr/inria-00555588/document https://hal.inria.fr/inria-00555588/document

alextheparrot 6y ago
This was 100% the path I think I was traveling (Thank you for the link). I had a hard time grocking the complete specification from the paper, but the README of this repository that implements CRDTs in that frame was helpful [1]. The core part is separating the "merge" from the "resolve" state. Merging state can be done in a variety of ways, so in the default formulation there seems to be a focus on making the "merge" operation also "resolve" to only one value, when really there could be multiple formally valid merges that the client may desire (Which is part of the difficulty that the video notes as he proposes a variety of possible file system mutations for a set of two uncoordinated operations). The cleanest clarification of my thought process is similar to the following: Given the operation Merge(4, 2), I could propose that there are two valid ways to perform this merge, addition and multiplication. This means the result would be either 6 or 8. The act of returning a single value (6 or 8) changes that proposal into a statement, though, which is the "resolve". One subversion of this restriction is to return a set of all possible results for the operations we think are valid, so {6, 8}. At this point, the user can say (Either explicitly or implicitly) "I actually want 6" and we resolve it to the single value of {6}. There are also special cases like Merge(2, 2), where this whole situation is especially ergonomic because the merge operations are equivalent. There are problems, of course, with this approach. One issue is the need to categorize all possible operations the user may think are valid for Merge(4,2). If the user intended to do division, the result set proposed above will not include the state that they would expect. Still, this seems more general now, as we just need to gather the set of operations that the user may think are valid instead of assuming which one is valid. There's also a ranking problem that then exists at the UX level, as we need to find a way to cleanly propose this set of alternatives. Another issue is, of course, exists if both users propose conflicting resolutions (Actor1 says "I want multiplication" and Actor2 says "I want addition"). This is the issue with decoupling the "merge" and "resolve" steps, as now we may cause a fork in the model which causes a fundamental divergence of the collaborator's data. [1] https://github.com/rust-crdt/rust-crdt https://github.com/rust-crdt/rust-crdt
macawfish 6y ago
Oh wow! I've been studying CRDTs for a year but never understood what a multi-value register would be used for, so I'd ignored it... But I get it now. Also because it sounded like a concept from the 70s or something.

rst 6y ago

This might be a reasonable UX in some cases -- but it seems to assume that whichever user chooses an alternative also gets to broadcast that choice and have it immediately binding on all the others -- which is incompatible with some use cases for CRDTs. Failing that, you've just kicked the can down the road. Consider two users A and B who make conflicting edits, and so wind up being presented with one of these choices. If they choose different options, and then make further edits, what do they see of each others' subsequent edits, and how do you explain the whole branched history to user C, who was out to lunch while this happened?

alextheparrot 6y ago
It does kick it down the road, but it also doesn’t make it unresolvable — one issue the video seemed to articulate is that the writer of the “merge” function needs to make a choice for the user about what “combine” looks like which is often the root of weird UX. The idea here was “Maybe we can not make a choice, but still expose valid results to the user so that they can make a choice”. It definitely isn’t fully fleshed our, though