5 ms·

Hi! Author of Eg-walker & ShareJS here, both of which are referenced by this post. You write this article like you're disagreeing with me - but I agree complet

Hi! Author of Eg-walker & ShareJS here, both of which are referenced by this post. 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 https://news.ycombinator.com/item?id=19889174

satvikpendem 2y ago
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 https://news.ycombinator.com/item?id=42343953#42344880
- josephg 2y ago
  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.
  - mkl 2y ago
    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 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 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-eg-walker https://loro.dev/blog/v1.0#leveraging-the-potential-of-the-e...
  - dmurray 2y ago
    > 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"
    - josephg 2y ago
      > 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.
CalebJohn 2y ago
> 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/ https://josephg.com/blog/crdts-go-brrr/
- crabmusket 2y ago
  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
  - CalebJohn 2y ago
    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.
    - josephg 2y ago
      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.
antics 2y ago
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.
- josephg 2y ago
  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.
  - lifeisstillgood 2y ago
    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
gritzko 2y ago
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.
ashoeafoot 2y ago
What i would love is, if the edit conflict was already baked into the language . Conflict<Implementation1, Implementation2>.
- GTP 2y ago
  What would be the advantage vs having an UI that clearly shows the conflict?
  - ashoeafoot 2y ago
    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.
barrystaes 2y ago
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.
- josephg 2y ago
  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.
  - hinkley 2y ago
    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.
    - 2y ago
chrismorgan 2y ago
> 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!
- WesolyKubeczek 2y ago
  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.
- joakims 2y ago
  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 https://news.ycombinator.com/item?id=42349264
  - chrismorgan 2y ago
    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.
    - josephg 2y ago
      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!"
kjrfghslkdjfl 2y ago
[dead]

satvikpendem 2y ago

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 https://news.ycombinator.com/item?id=42343953#42344880

josephg 2y ago
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.
- mkl 2y ago
  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 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 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-eg-walker https://loro.dev/blog/v1.0#leveraging-the-potential-of-the-e...
- dmurray 2y ago
  > 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"
  - josephg 2y ago
    > 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.

CalebJohn 2y ago

> 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/ https://josephg.com/blog/crdts-go-brrr/

crabmusket 2y ago
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
- CalebJohn 2y ago
  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.
  - josephg 2y ago
    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.

antics 2y ago

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.

josephg 2y ago
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.
- lifeisstillgood 2y ago
  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

gritzko 2y ago

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.

ashoeafoot 2y ago

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

GTP 2y ago
What would be the advantage vs having an UI that clearly shows the conflict?
- ashoeafoot 2y ago
  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.

barrystaes 2y ago

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.

josephg 2y ago
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.
- hinkley 2y ago
  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.
  - 2y ago

chrismorgan 2y ago

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

WesolyKubeczek 2y ago
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.
joakims 2y ago
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 https://news.ycombinator.com/item?id=42349264
- chrismorgan 2y ago
  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.
  - josephg 2y ago
    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!"

kjrfghslkdjfl 2y ago

[dead]