So this is either represented as a delete followed by an insert (delete one character at offset N, insert "m" at offset N), or as a replace (atomically replace character at offset N with "m").
For an atomic replace operation, CRDT algorithms will solve this by having the last write win. What CRDTs give you here is a guarantee that the order is the same for every participant. So if you're building a collaborative text editor, for example, either everyone will either see "moo" or everyone will see "boo".
For a delete + insert, it might not be atomic, in which case only the delete will "conflict". Since you both deleted at the same time, it's not actually a conflict (you both did the same thing), and the result will be either "mboo" or "bmoo". But again, it will the same for everyone.
Interesting. What about the seqeunce "Alice deletes f, Bob replaces f with b, Alice inserts m"? I guess it doesn't matter, as long as all implementations do the same thing.
git could easily take an approach like this too, but there are obvious reasons why it doesn't. It feels like the people designing this algorithm believe the text being worked on is less important than source code.
I don't see how it's possible. I get Alice's changes, I spend 3 hours working on them, I get Bob's changes. The algorithm might be able to resolve these three sets of changes consistently according to its rules, but I've got no faith that the meaning of the text would survive the process.
CRDTs work best for high-contention situations such as online text editing (think Google Docs) where the conflict resolution can be seen right away and addressed by the user.
For offline sync, where someone edits a text document for an hour and then syncs, you're right: You can end up with something unintended, since each participant is editing based on ("branching off") a snapshot. For example, if I deleted a whole paragraph, and you edited it, what should the end result be? But at least the end result will be consistent in the sense that all participants end up seeing the same thing, though semantically it may be wrong.
Note that CRDTs go beyond just text. CRDTs can be used to represent arbitrary data structures and operations on them: Array s (insert, delete, append, etc.), numbers(increment, decrement, etc.), dictionaries (insert, delete), etc. A great implementation of this is Automerge [1].
That makes sense, and is reasonable. Thank you for taking the time to explain. I am now wondering about the space where CRDTs and databases overlap.
(Very unformed thoughts follow) We're used to databases storing the system's current state. If we're lucky, we're writing changes to the database, rather than just the current state, so we can reconstruct the system's state at any point in the past. What would a database that not only stores changes but also resolves conflicts look like, I wonder. A database where CRDT was a column type, I guess.
Further thought: A list of deltas in a database is reversable - you can wind back to see what the database state was 3 weeks ago. Can you reverse a CRDT?
I'm not sure why I keep coming back to this. Maybe because it's a new structure I've never thought about before. Maybe I'll have to implement one, just to get a feel for them.
> either everyone will either see "moo" or everyone will see "boo"
That seems in conflict with the claim elsewhere in this discussion that this works offline, too (https://news.ycombinator.com/item?id=23802495)
I guess everyone will eventually either see “moo” or “boo”?
So, literally a change nobody wanted? Seems like it would not work in any real sense. I change it to moo and as a line checking something on it. You change it to boo and add a line, as well. Congrats, now neither of our additional lines makes sense...
This really feels like a solution in search of problems.
> Congrats, now neither of our additional lines makes sense...
What would you expect to happen? That one persons input is ignored? That’s hardly expected for that person. If anything, it’s much more confusing. This way, both people see both Ed it a and can react appropriately. If they both remove the same thing, then no problem, if they keep stomping on each other’s work, then they need to communicate anyway.
The important thing isn’t that you ended up with something neither of you wanted but that it’s consistent for all people. You see the exact same thing they see.
> This really feels like a solution in search of problems.
Hardly. As someone who once wrote a collaborative editor as a you project long ago, this seems really useful to me. I’ve also worked on mobile sync (multiple devices that could be edited offline syncing with the online version) and again this would have been really beneficial as the solution being used wasn’t great at all.
Don't ignore, but just like I expect my car to not start of I don't have my foot where it is supposed to be, I'd expect there editor to indicate to me that my edit could not go through.
And I think I wasn't clear. Collaborative editors at the character level feel like the solution that is a misfire. Doing the same things at a higher level of abstraction works. Merge in document changes in remote sections. Code merges with git work reasonably. None are bullet proof, and I expect conflicts at a level lower than paragraph to almost always need an audit. Certainly lower than the line level.
This is how google docs works and this problem doesn’t come up much in practice. The reason is that usually when you’re collaboratively editing a document you do so in real-time. If we both see one another’s cursor on the same content, we pay extra attention and make sure our edits make sense.
For offline edits (eg multiple developers working on independent features in a codebase), generating merge conflicts is probably more appropriate. OT and CRDTs can be written that generate merge conflicts in cases like this - it’s an implementation detail. It’s just that most algorithms are written first and foremost with real-time collaborative editing in mind. And again, in the real-time collaborative editing case, merge conflicts aren’t what users want.
I recently did realtime collaborative editing of the same file with a Visual Studio Code plugin and have also often used Google Docs and its really not an issue in practice. If it were to suddenly stop me to notify me that there was a conflict, that would be a very jarring and unpleasant workflow.
As josephg says, you don’t want merge conflicts in realtime editing and for offline editing, a git merge conflict resolution style is probably more appropriate.
It’s an extremely valuable solution to a very real problem. Surely you must have tried Google Docs? The “mboo” is an indication that the two editors have different ideas about where they’re going. In a typical setup both editors will see that someone else has their cursor in the same place in the document, and they will very quickly see that a conflict has happened. Now they can coordinate on how to resolve it. It’s not a problem, but a desirable step in the process of two people working together on something that isn’t finished.
I've seen all to often where people don't see the conflict because it allowed them to continue.
Such that editing a Google doc is easily up there with many other experiences I don't like. Taking the act of editing, that used to just be single user and forcing it into distributed tricks from the get go.
Yes, collaboration is distributed. And sometimes it is nice to both be working at the same place/time. Usually, though, a batch process is easier to reason about and execute.
A text editor could easily highlight passages where concurrent changes were made. (Perhaps only if a heuristic indicates that the merged change doesn’t make any sense.) The metadata is all there.
That's the best failure mode you can expect for the average user without diving into the usability pit that is git - both changes are kept and it's obvious to users that there is a merge conflict. Otherwise, one update would just eat the other silently, leaving one side confused and the other oblivious.
Things are always sequenced. One will win, and the other will have to redo their change on top. Partially applying the change at the word level just seems way too fraught with false edits. It is already a source of a lot of bugs at the file and project level.
But one person edited the word foo. The other edited a weird that no longer exists. I get why this feels like a clever combination of the edits. But I'm struggling to see how doing this at the character level makes any sense.
Consider instead that you could do this at the byte level, with equally off results.
At higher levels, this trick sounds useful. But you pick your abstraction height where all conflicts should just go back to the user.
So, people edit the same document, but at different paragraphs? Fine. They edit the same paragraph? Almost certainly a problem. No different than code.
Different strategies have different tradeoffs and work better for different use cases. If you have multiple people interactively editing the same document (i.e. syncs are happening regularly), it can feel more natural to err on the side of applying each user's edits and letting the humans work it out, rather than flagging a conflict that must be resolved before proceeding. When using Google Docs I've had the occasional awkward "after you, no after YOU" moment while trying to edit the same text, but it's pretty rare. You obviously wouldn't want to use this same approach for asynchronous/offline collaboration, where more explicit conflict resolution like a VCS offers is necessary.
The place where this kind of character-level approach actually does start to fall apart is when users can make larger structural changes to the document with single actions -- reordering lists, cutting and pasting chunks of text, etc. There are other options for that.
