CRDTs: Convergence without coordination
read.thecoder.cafe
CRDTs: Convergence without coordination
1–10 of 34 posts
Re: CRDTs: Convergence without coordination
#2The article sets up a scenario where two people are editing a document, but have conflicting changes: "If Alice fixes a missing letter in a word while Bob removes the whole word, that’s a conflict."
The article then goes into some examples of CRDTs and their merge operation, and the examples are pretty straightforward: take the maximum of two values, or take one with a more recent timestamp, etc.
But what about the motivating example? What should a merge function do with the inputs "change the third word from 'affect' to 'effect'" and "delete the third word"? In other words, how does the function know which of these operations "wins"? It could ask a user for a manual resolution, but is there a reasonable way for a function to make this determination itself? Maybe deletes are more powerful than word changes, so the delete wins.
Re: CRDTs: Convergence without coordination
#3The article sets up a scenario where two people are editing a document, but have conflicting changes: "If Alice fixes a missing letter in a word while Bob removes the whole word, that’s a conflict." The article then goes into some examples of CRDTs and their merge operation, and the examples are pretty straightforward: take the maximum of two values, or take one with a more recent timestamp, etc. But what about the m…
There is no objectively correct way to do the merge, but there are ways that are obviously wrong.
Re: CRDTs: Convergence without coordination
#4Loro is the open source project I am most excited about, their documentation is also stellar as an intro to the subject.
As an aside, I find FugueMax to be amazing to solve interleaving issues.
I've found for collaborative editing fuguemax for resolving intraline edits and h-lseq for the lines themselves has been amazing.
Re: CRDTs: Convergence without coordination
#5The article sets up a scenario where two people are editing a document, but have conflicting changes: "If Alice fixes a missing letter in a word while Bob removes the whole word, that’s a conflict." The article then goes into some examples of CRDTs and their merge operation, and the examples are pretty straightforward: take the maximum of two values, or take one with a more recent timestamp, etc. But what about the m…
I think it's your job as a designer to encode which update should win. In case of equivalent updates like writing to a field they suggest 'last update wins" strategy.
For words, if a word is a single unit in your system, delete obviously beats amendment.
Re: CRDTs: Convergence without coordination
#6The article sets up a scenario where two people are editing a document, but have conflicting changes: "If Alice fixes a missing letter in a word while Bob removes the whole word, that’s a conflict." The article then goes into some examples of CRDTs and their merge operation, and the examples are pretty straightforward: take the maximum of two values, or take one with a more recent timestamp, etc. But what about the m…
I mean your example is a classic case.
And there are different algos, for diamondtypes:
Once a character is seen by clients any delete of it wins, algos like diamond types reconstruct each clients stream.
So in the case of DT, effect is absolutely gone, two clients deleting the e and one client deleted the ffects, and they both started at the same causal slice, but the A is a good question. You might just end up with an A.
In the case of multiple inserts in the same position dt uses the client ids lexical sort for ordering to reduce text interleaving.
Other crdt approaches may be positional or last write wins, in which case you may end up with nothing.
Besides being an amazing project loro crdts documentation and blog covers a lot of this stuff and names the specific algos they use.
Re: CRDTs: Convergence without coordination
#7The article sets up a scenario where two people are editing a document, but have conflicting changes: "If Alice fixes a missing letter in a word while Bob removes the whole word, that’s a conflict." The article then goes into some examples of CRDTs and their merge operation, and the examples are pretty straightforward: take the maximum of two values, or take one with a more recent timestamp, etc. But what about the m…
I think it's your job as a designer to encode which update should win. In case of equivalent updates like writing to a field they suggest 'last update wins" strategy. For words, if a word is a single unit in your system, delete obviously beats amendment.
> suggest 'last update wins" strategy.
Hmm, last update as it's received by a central server? Last update according to the time on the device doing committing the update? The rabbit hole just keeps going, for each decision you get multiple new edge cases with unintended behavior...
Re: CRDTs: Convergence without coordination
#8Earlier quoted context omitted.
I think it's your job as a designer to encode which update should win. In case of equivalent updates like writing to a field they suggest 'last update wins" strategy. For words, if a word is a single unit in your system, delete obviously beats amendment.
> suggest 'last update wins" strategy. Hmm, last update as it's received by a central server? Last update according to the time on the device doing committing the update? The rabbit hole just keeps going, for each decision you get multiple new edge cases with unintended behavior...
Sounds like a job for a block chain!
Re: CRDTs: Convergence without coordination
#9Earlier quoted context omitted.
I think it's your job as a designer to encode which update should win. In case of equivalent updates like writing to a field they suggest 'last update wins" strategy. For words, if a word is a single unit in your system, delete obviously beats amendment.
> suggest 'last update wins" strategy. Hmm, last update as it's received by a central server? Last update according to the time on the device doing committing the update? The rabbit hole just keeps going, for each decision you get multiple new edge cases with unintended behavior...
CRDTs mostly have a time notions like Lamport clocks, vector clocks, ... not actual device time => see more here: https://adamwulf.me/2021/05/distributed-clocks-and-crdts/
Re: CRDTs: Convergence without coordination
#10Earlier quoted context omitted.
I think it's your job as a designer to encode which update should win. In case of equivalent updates like writing to a field they suggest 'last update wins" strategy. For words, if a word is a single unit in your system, delete obviously beats amendment.
> suggest 'last update wins" strategy. Hmm, last update as it's received by a central server? Last update according to the time on the device doing committing the update? The rabbit hole just keeps going, for each decision you get multiple new edge cases with unintended behavior...
It's most likely causality-based time, not the time per an atomic clock.