[HN Gopher] CRDTs: Convergence without coordination
___________________________________________________________________
CRDTs: Convergence without coordination
Author : 0xKelsey
Score : 75 points
Date : 2025-10-16 15:00 UTC (7 days ago)
(HTM) web link (read.thecoder.cafe)
(TXT) w3m dump (read.thecoder.cafe)
| cbm-vic-20 wrote:
| 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 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.
| swid wrote:
| There is no objectively correct way to do the merge, but there
| are ways that are obviously wrong.
| scotty79 wrote:
| 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.
| ffsm8 wrote:
| > 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...
| bux93 wrote:
| Sounds like a job for a block chain!
| gregoriol wrote:
| 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/
| ffsm8 wrote:
| 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
| heromal wrote:
| It's most likely causality-based time, not the time per an
| atomic clock.
| SkiFire13 wrote:
| 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.
| fellowniusmonk wrote:
| 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.
| jongjong wrote:
| 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.
| edbaskerville wrote:
| 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.
| staplung wrote:
| 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.
| aaronblohowiak wrote:
| 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!)
| dkarl wrote:
| 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.
| fidotron wrote:
| 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?
| gorgoiler wrote:
| 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.)
| fellowniusmonk wrote:
| Loro 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.
|
| https://loro.dev/blog/crdt-richtext
| deepanwadhwa wrote:
| Does anyone know if there is anything like CRDT with end to end
| encryption?
| schainks wrote:
| You mean something like this?
| https://jakelazaroff.com/words/homomorphically-encrypted-crd...
|
| It is slow and inefficient, but can be done.
| sotomski wrote:
| 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
| marcusestes wrote:
| Fireproof implements a CRDT and implements E2E. https://use-
| fireproof.com/docs/welcome/
| Retr0id wrote:
| 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
| niko-ng wrote:
| 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/
| johnofthesea wrote:
| https://p2panda.org/2025/02/24/group-encryption.html
| Arcuru wrote:
| 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
| brunoqc wrote:
| Yeah, CRDT seems to be the holy grail for p2p local-first apps.
|
| I dream about this.
| ellieh wrote:
| this is so cool! really excited to see where it goes
| iwontberude wrote:
| 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.
___________________________________________________________________
(page generated 2025-10-23 23:01 UTC)