Hacker News new | past | comments | ask | show | jobs | submit login

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




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


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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: