Hacker News Reader

> 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.

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!

I am partial to conflict resolution via trial by combat. Very ancient technology, and while it doesn’t always work well, it works every time.

As crabmusket said [1], I think the C should stand for Commutative, as it apparently did once. Commutative Replicated Data Types, conflict management optional.

[1] https://news.ycombinator.com/item?id=42349264

See my response to that comment now—it’s actually largely incorrect. If you look at it through an operations lens, commutativity is what matters and convergence is meaningless, but if you look through a state lens, there’s no such thing as commutativity, convergence is what matters. So choosing another word that describes the overarching property, that conflicts cannot occur, is quite reasonable.

Even looking through a state lens, I think the commutativity requirement makes sense to think about.

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!"

Hi Joseph! I am sorry, I was not trying to say your work sucks. I was trying to (1) help practitioners understand what they can expect, and (2) motivate problems like the one you mention at the end.

(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.

No need to apologise or change your article or anything. I think it’s great! It’s true that I haven’t written any articles or blog posts about this problem. People absolutely will appreciate more discussion and awareness of this problem, and I’m delighted you’re getting people talking about it.

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.

I just want to congratulate you both for contributing to the sum of human knowledge and understanding without resorting to entrenched positions, a rarity in todays online discourse. Great to read positive attitudes

> 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!

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?

[1] https://josephg.com/blog/crdts-go-brrr/

That is what josephg was suggesting:

> it should be very possible to build a CRDT which uses this information to detects & mark conflict ranges when branches are merged

I should have been more clear in my original comment.

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.

I’m not sure I agree that that approach would work. There’s two reasons:

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.

Do you think that a LLM/"AI" can reliably solve the merging problem?

> Do you think that a LLM/"AI" can reliably

No. LLMs definitely have uses where reliability is not a requirement, but that's one requirement which LLMs clearly never meet

The author describes the case of overlapping concurrent splices. It is a known funky corner case, yes. If we speak of editing program code, the rabbit hole is deeper as we ideally expect a valid program as a result of a merge. There was a project at JetBrains trying to solve this problem through AST-based merge. After delving into the rabbit hole much much deeper, the guys decided it is not worth it. This is what I was told.

I would simply argue that the “offline” editing is a people-problem and hence van not be solved using automation. People shall find a way to break/bypass the automation/system.

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.

Yes I agree. But remember: but git will automatically merge concurrent changes in most cases - since most concurrent changes aren’t in conflict. You’re arguing you want to see & review the merged output anyway - which I agree with.

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.

The tricky thing about “most” is that it means more than half, but people tend to treat it like almost all.

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.

I think it's just a UX problem. Once that is solved, which I believe is definitely possible, both CRDTs and git can be made much more user friendly. I'm not saying it's easy, because it hasn't been solved yet, but I don't think the right people have been working on it. UX is the domain of designers, not engineers.

I think we are sitting at about 75% on one of those problems that will go asymptotic at 90%.

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.

> 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.

How is this different than git's automatic merging? Or another compatible algorithm

In the happy case? Its no different. But in the case where two offline edits happen at the same location, Git's merging knows to flag the conflict for human review. Thats the part that needs to be fixed.

It's not clear to me what you want to replace from git then, it seems to me that you rather want to take concepts from git.

I want a tool with the best parts of both git and a crdt:

- 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.

I mentioned Loro in another comment which uses EG Walker, do you think they are an example of what you had mentioned? This comment also seems relevant [0].

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.

[0] https://news.ycombinator.com/item?id=42343953#42344880

Does Loro generate conflict ranges when merging branches, thus allowing manual conflict resolution?

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.

It seems that they might, but perhaps not in a good way yet, and they have it as a goal.

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...

> but CRDTs work because the same computation on two peers is guaranteed to produce the same result. LLMs can’t guarantee that.

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"

> 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.

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.

Loro is planning on doing so, as the other comment says. Related, is this what you are looking for [0]? The commenter says that their implementation will surface conflicts to the user.

[0] https://news.ycombinator.com/item?id=42348381

What i would love is, if the edit conflict was already baked into the language . Conflict<Implementation1, Implementation2>.

What would be the advantage vs having an UI that clearly shows the conflict?

It would allow for identification of intent and reasoning over that.

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.