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

21–30 of 34 posts

Re: CRDTs: Convergence without coordination

#21

Post by dkarl »

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…

I think people who haven't worked on problems like this have much higher expectations than people who have.

If you have worked on problems like this, you're very happy to converge on the same state and have no expectation that multiple concurrent editors will be happy with the result. Or even that one of them will be happy with the result.

You wouldn't use this in a situation like version control where you have to certify a state as being acceptable to one or multiple users.

Re: CRDTs: Convergence without coordination

#22

Post by SkiFire13 »

scotty79 wrote: post #5
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…

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.

This only works for very simple cases where there is already an existing strategy, but I have yet to see strategies for more complicated cases, especially ones where you also need to preserve some kind of consistency. Ultimately this boils down to "write your own CRDT", where CRDT is no longer a tool but just a definition to satisfy.

Re: CRDTs: Convergence without coordination

#23

Post by brunoqc »

Arcuru wrote: post #19

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

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

I dream about this.

Re: CRDTs: Convergence without coordination

#24

Post by ffsm8 »

gregoriol wrote: post #9
ffsm8 wrote: post #7

Earlier quoted context omitted.

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

All of which have their own weaknesses. And all of them can suffer the split brain scenario.

And all but the last one fundamentally have lots of edge cases with e.g. high-latency sync

Re: CRDTs: Convergence without coordination

#25

Post by edbaskerville »

jongjong wrote: post #11
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…

I think the really interesting problem in this space is designing UIs and data structures that, on the one hand, capture as much user intent as possible, but, more importantly, make it easier for users to manage conflicts.

I.e., if there's a tricky conflict, the app need not resolve it at all. Rather, it should provide, by default, a nice way for the user to manage the resolution as part of the normal workflow.

Or, phrased another way, conflicts aren't conflicts. Parallel, "conflicting" edits are simply a state of affairs that is inherent to the process, and are still reflected in the data structure after merging all edits.

How this would actually look would probably vary from domain to domain. But my general philosophy on this stuff is that if complexity is real and potentially important to the user, the software should expose the complexity and enable the user to manage it, not force a simplification that hides something important.

Re: CRDTs: Convergence without coordination

#26

Post by niko-ng »

deepanwadhwa wrote: post #13

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

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/

Re: CRDTs: Convergence without coordination

#27

Post by fidotron »

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…

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?

Re: CRDTs: Convergence without coordination

#28

Post by ellieh »

Arcuru wrote: post #19

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

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

Re: CRDTs: Convergence without coordination

#29

Post by gorgoiler »

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…

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.)

Post reply on HN