Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

CRDTs: Convergence without coordination

read.thecoder.cafe

Post reply on HN
Print view View original

11–20 of 34 posts

Re: CRDTs: Convergence without coordination

#11

Post by jongjong »

cbm-vic-20 wrote: post #2

The 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…

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.

Re: CRDTs: Convergence without coordination

#12

Post by staplung »

cbm-vic-20 wrote: post #2

The 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…

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.

Re: CRDTs: Convergence without coordination

#15

Post by sotomski »

deepanwadhwa wrote: post #13

Does anyone know if there is anything like CRDT with end to end encryption?

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

Re: CRDTs: Convergence without coordination

#18

Post by aaronblohowiak »

staplung wrote: post #12
cbm-vic-20 wrote: post #2

The 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…

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 wo…

to add on to that, it is that the resolution is the same regardless of the order in which the nodes get the information that led to the conflict so there is no "out of sync". your resolution strategy could involve considering the potential conflict unresolved until a resolution element is created (but then you have to figure out what to do if you get more than one of those.. its conflicts all the way down!)

Re: CRDTs: Convergence without coordination

#19

Post by Arcuru »

Shameless plug: I'm betting that a lot of applications could use some form of CRDT as a Database, which would allow a fully decentralized backend/database for local-first apps. So I've been building one.

Still working on good blog posts to explain and introduce it though.

https://github.com/arcuru/eidetica

Re: CRDTs: Convergence without coordination

#20

Post by iwontberude »

The toy example with two nodes incrementing and decrementing likes independently and then sharing the delta with each other would require an increasing amount of backend requests (n^2) for every like. If you had 10000 nodes and they were all sending 9999 requests to eachother for a single request, obviously that's not the best model. It did somewhat remind me of MySQLs active-active replication scheme but that has some locking to make sure drift isn't too bad. MySQL Group Sync also doesn't scale beyond 9 nodes.
Post reply on HN