Regarding your [1], I had a similar idea and I am beginning to think that only something like an LLM or similar can truly merge conflict free because only they are powerful enough to understand users' intent.
I’ve heard people suggest using LLMs for years for this - but CRDTs work because the same computation on two peers is guaranteed to produce the same result. LLMs can’t guarantee that. You could probably use an llm in leu of a human manually merging conflicts - but in that case we still need the crdt to first generate those conflict ranges to pass to the llm. Essentially an llm could solve the UX problem, but the underlying algorithm still needs this feature first to allow that to be used.
From https://loro.dev/blog/v1.0#next-steps-for-loro:
> When merging extensive concurrent edits, CRDTs can automatically merge changes, but the result may not always meet expectations. Fortunately, Loro stores the complete editing history. This allows us to offer Git-like manual conflict resolution at the application layer when needed.
From https://loro.dev/docs/tutorial/time_travel:
> once we have a more refined version control API in place.
I'm interested to hear your opinion of their partial adoption of Eg-walker: https://loro.dev/blog/v1.0#leveraging-the-potential-of-the-e...
This doesn't seem like a hard requirement. It's a nice property for some academically interesting peer-to-peer trustless algorithm, but in typical software architectures you won't get a situation where Alice receives Bob's edits and Bob receives Alice's edits without them passing through a centralised server that can reconcile them first.
In any case, LLMs can be run deterministically (temperature=0, or use a fixed random seed and a single core where necessary).
I don't expect further serious work in the offline text editing space. The next generation will certainly be some form of "guess, then ask an LLM to guess"
Thats the exact situation these algorithms are all designed to handle. If you require a centralised reconciling server, you’re taking a big step back in functionality - and you no longer have an eventually consistent system.
But as I say, asking an llm - what exactly? Most of the time concurrent edits are in different regions of a document and you want them to be merged automatically in the obvious way. It’s only when the same text (same line) is edited by two peers that you want to invoke a llm (if at all). If that’s the case you still need the crdt to detect conflicting ranges - you’re just using an llm instead of a human to resolve them. And in that case, CRDTs are still missing the important feature this blog post talked about. You’re just proposing a different UX layer on top of that missing feature.
And really, you’ll probably still want human review. LLMs have a tendency to do drive-by edits in situations like this, adding or removing commas in prose, changing formatting in code and so on. I don’t trust LLMs to touch my code or my writing without human review.
I'm skeptical that an algorithmic solution will be possible, but I can see this being handled in a UX layer built on top. For example, a client could detect that there's been a conflict based on the editing traces, and show a conflict resolution dialog that makes a new edit based on the resolution. The tricky part is marking a conflict as resolved. I suspect it could be as simple as adding a field to the crdt, but maybe then it counts as an algorithmic solution?
> it should be very possible to build a CRDT which uses this information to detects & mark conflict ranges when branches are merged
I don't think that the conflict detection/resolution needs to live inside the CRDT data structure. Ultimately you might want to bake it in out of convenience, but it should be possible to handle separately (of course the resolution will ultimately need to be written to the CRDT, but this can be a regular edit).
Keeping the conflict resolution in the application layer allows for CRDT libraries that don't need to be aware of human-in-the-loop conflicts, and can serve a wider range of downstream needs. For example, a note app and a version control system might both be plain text, but conflict resolution needs to be handled completely differently. Another example would be collaborative offline vs. online use cases, as noted above, they are very different use cases.
1. The crdt has an awful lot of information at its disposal while merging branches. I think “branch merging” algorithms should ideally be able to make use of that information.
2. There’s a potential problem in your approach where two users concurrently merge branches together. In that case, you don’t want the merges themselves to also conflict with one another. What you actually want is for the standard crdt convergence properties to hold for the merge operation itself - and if two people concurrently merge branches together (in any order) then it all behaves correctly.
For that to happen, I think you need some coordination between the merging and the crdt’s internal data structures. And why not? They’re right there.
A sketch of a solution would be for the merge operation to perform the normal optimistic merge - but also annotate the document with a set of locations which need human review. If all peers use the same algorithm to figure out where those conflict annotations go, then the merge itself should be idempotent. The conflict annotations can be part of the shared data model.
Another, maybe simpler approach would be for the crdt library itself to just return the list of conflicting locations out of band when you do a merge operation. (Ie, we don’t change the crdt data structure itself - we just also return a list of conflicting lines as a return value from the merge function). The editor takes the list of conflicting locations and builds a ui around the list so the user can do manual review.
No. LLMs definitely have uses where reliability is not a requirement, but that's one requirement which LLMs clearly never meet
(1) might seem stupid but I think just evaluating these systems is a challenging enough technical problem that many teams will struggle with it. I just think they deserve practical advice—I know we would have appreciated it earlier on.
I’m motivated by wanting the problem solved, not getting the most praise by random people on the internet. If today that means being cast in the role of “the old guard who’s missing something important” then so be it. What fun.
Is it aggregate, the people adding to the same with no overlaping elements.
Is it a overlapping set, n-people contributing the same
Is it a xor set where two people want to split up a implementation and go into different directions ?
If one deletes and creates a new as replacement , the other continues to work on the element, that could auto map to an intent above.
And if you know that you can provide much more resonable merges.
The only “offline editing” that I allow on human text documents is having people add comments. So not editing, no automated merging.
For “offline editing” that I allow on automation (source code) is GIT which intentionally does not pretend to solve the merge, it just shows revisions. The merge is an action supervised by humans or specialised automation on a “best guess” effort and still needs reviews and testing to verify success.
Ideally, I want to be able to replace git with something that is built on CRDTs. When branches have no conflicts, CRDTs already work fine - since you merge, run tests, and push when you’re happy.
But right now CRDTs are too optimistic. If two branches edit the same line, we do a best-effort merge and move on. Instead in this case, the algorithm should explicitly mark the region as “in conflict” and needing human review, just like git does. Then humans can manually review the marked ranges (or, as others have suggested, ask an llm to do so or something.). And once they’re happy with the result, clear the conflicting range markers and push.
I would agree that git works more than half the time.
Merge resolution is a problem so hard that even otherwise capable developers fuck it up regularly. And on a large team made of people who intermittently fuck up, we start getting into and aggregate failure rate that feels like a lot.
The whole idea with CRDTs was to make something humans couldn’t fuck up, but that seems unlikely to happen. There’s some undiscovered Gödel out there who needs to tell us why.
And that’s if you swap the default diff algorithm for one of the optional ones. I’ve used patience for years but someone tweaked it and called it “histogram” when I wasn’t looking.
How is this different than git's automatic merging? Or another compatible algorithm
- From CRDTs I want support for realtime collaborative editing. This could even include non-code content (like databases). And some developer tools could use the stream of code changes to implement hot-module reloading and live typechecking.
- From git I want .. well, everything git does. Branches. Pull requests. Conflict detection when branches merge. Issue tracking. (This isn't part of git, but it would be easy to add using json-like CRDTs!)
We can do almost all of that today. The one part that's seriously missing is merge conflicts.
So you end up with “conflict” as part of your data model. Seems an amusing way of achieving the C (“conflict-free”) of CRDT, though perfectly legitimate and probably the only way.
The next fun challenge is when you get conflicts over conflict resolution!
For example, one of the simplest state CRDTs is the MAX function. The commutativity rule requires that if we merge some set of states A, B, C, ... in any order, we get the same result. This requires the MAX function to be commutative - ie, MAX(a, b) == MAX(b, a). (And also MAX(a, b, c) == MAX(c, a, b), and so on.)
This must hold for the CRDT to converge & be correct.
I thought the C stood for commutativity for the longest time after learning CRDTs. I admitted that to Martin Kleppmann the first time I met him. He thought for a solid minute, then laughed and said "yeah, I think that works too!"
You write this article like you're disagreeing with me - but I agree completely with what you've said. I've been saying so on HN for years. (Eg, in this comment from 6 years ago[1].)
The way I think about it, the realtime collaborative tools we use today make a lot of sense when everyone is online & editing together. But when users edit content offline, or in long lived branches, you probably want the option to add conflict markers & do manual review when merging. (Especially for code.)
Luckily, algorithms like egwalker have access to all the information they need to do that. We store character-by-character editing traces from all users. And we store when all changes happened (in causal order, like a git DAG). This is far more information than git has. So it should be very possible to build a CRDT which uses this information to detects & mark conflict ranges when branches are merged. Then we can allow users to manually resolve conflicts.
Algorithmically, this is an interesting problem but it should be quite solvable. Just, for some reason, nobody has worked on this yet. So, thanks for writing this post and bringing more attention to this problem!
If anyone is interested in making a unique and valuable contribution to the field, I'd love to see some work on this. Its an important piece thats missing in the CRDT ecosystem - simply because (as far as I know) nobody has tried to solve it yet. At least not for text editing.
[1] Bottom part of this comment: https://news.ycombinator.com/item?id=19889174