CRDTs: Convergence without coordination

Yeah, CRDT seems to be the holy grail for p2p local-first apps.

I dream about this.

this is so cool! really excited to see where it goes

That looks awesome! Do you have any metrics on storage space and query/insert performance for large amounts of data? Building something that has couple of million rows.

There is no objectively correct way to do the merge, but there are ways that are obviously wrong.

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.

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.

Yes, it's impossible for a distributed system to figure out the collaborative intent when it sees conflicting changes... Even the people who made the changes may not 'know' what is the correct way to resolve the conflict... For that to happen, people involved would have to communicate and agree on either option or they would have to agree on a compromise. This problem cannot be solved automatically because computers cannot read minds (yet).

This is why I like using granular data structures where each value can be updated in an all-or-nothing manner and if one person's change overwrites another, the person whose change was overwritten will just assume that the other person made an update shortly after and the amount overwritten is minimal.

The "conflict-free" part of the name is misleading. The conflict "resolution" means having some deterministic algorithm such that all nodes eventually converge to the same state, but it won't necessarily mean that the end state looks like it's conflict-free to a human. The algorithm you choose to implement will determine what happens in the editing case imagined; various answers are possible, perhaps most of which would be classified as conflicting changes by a human who looked at the final result. The pitch for CRDTs is "we won't trouble you with the replication details and will eventually converge all the changes. The tradeoff is that sometimes we'll do the wrong thing."

That tradeoff is fine for some things but not others. There's a reason why git et al require human intervention for merge conflicts.

The article is doing a classic bait-and-switch: start with a motivating example then dodge the original question without pointing out that CRDTs may be a very bad choice for collaborative editing. E.g. maybe it's bad for code and legalese but fine for company-issued blog posts.

CRDTs really provide a nice formalism for reasoning about design choices in this space, almost more so than being a practical solution in and of themselves. For your example operational transformations have long been used as the way to go.

My experience of CRDTs is it rapidly descends into a question of defining if two things are in fact equal or merely look equal. i.e. if two people concurrently add "this is a new item" to a set did they create two separate items or the same thing?

Is the answer clearer if you consider two changes, A to B and A to X? The conflict free result is to change A to BX, distribute this to every node, and let the people decide. (This is what Automerge does?)

(Deleting a word is just changing it from word to ~word~ with the option to render conflict free deletions as empty space.)

You mean something like this? https://jakelazaroff.com/words/homomorphically-encrypted-crd...

It is slow and inefficient, but can be done.

AFAIK, Automerge people work pretty hard on Beehive and Keyhive. Once released, that’ll be exactly what you asked for: https://www.inkandswitch.com/keyhive/notebook/05/ You can also use Yjs over Matrix (which has e2e encryption): https://github.com/YousefED/Matrix-CRDT

Fireproof implements a CRDT and implements E2E. https://use-fireproof.com/docs/welcome/

In theory, you can exchange CRDT update information over any channel you like (say, MLS) https://martin.kleppmann.com/2019/05/15/encrypted-crdts.html

another shameless plug: there is NextGraph.org which does exactly tha: E2EE CRDTs. It supports Automerge and Yjs (and soon Loro). It is being used already by several apps. The SDK will be released in November. Stay tuned by following us on https://fosstodon.org/@nextgraph and subscribing to our mailinglist https://nextgraph.org/