Technical Debt's avatar
Technical Debt technicaldebt@poster.place 2 weeks ago
From
Conflict-free Replicated Data Types
About CRDTs • Conflict-free Replicated Data Types
Resources and community around CRDT technology — papers, blog posts, code and more.
 > Conflict-free Replicated Data Types (CRDTs) are used in systems with optimistic replication, […] CRDTs ensure that, no matter what data modifications are made on different replicas, the data can always be merged into a consistent state. This merge is performed automatically by the CRDT, without requiring any special conflict resolution code or user intervention. > Moreover, an important characteristic of CRDTs is that they support decentralised operation: they do not assume the use of a single server, so they can be used in peer-to-peer networks and other decentralised settings. In this regard CRDTs differ from the algorithms used by Google Docs, Trello, and Figma, which require all communication between users to flow via a server. Practical example: instead of republishing a follow list every time I follow or unfollow someone, I make a follow event with the npub I am interested in following (or unfollowing). Then my client can compute the follow list locally, from the follow and unfollow events. Suppose that I follow someone from a desktop client but the event did not propagate to every relay I use and/or my phone has been disconnected from the internet for a long time and/or it can only connect to the other half of relays etc and I decided to follow someone, it is just an event. When connectivity normalizes or you sync your phone with your computer directly over bluetooth (amethyst) or FIPS (nostr vault), they will accept each other’s follow events and converge into the same computed follow list - all without special casing, conflict resolution code (like nostur has) and overall it has less complexity and more guarantees than the proposed “event chains”. I also suppose it would make calculating follow counts easier (rather than inspecting an unbound number of follow lists you could just request follow/unfollow events filtered by npub).
↑ Parent

Replies (6)

Roger's avatar
Roger roger@nostrcheck.me 2 weeks ago
Kind 3 already is a CRDT in the narrow sense: a last-writer-wins register per pubkey, ordered by created_at. That is exactly why it loses data silently. Newest write wins, and it cannot tell 'the event never reached me' apart from 'I unfollowed'. Your example needs the piece kind 3 lacks: a version vector or per-entry tombstones. Add tombstones and the merge is well defined. Skip them and any union merge resurrects unfollows, so clients that tried ended up with special casing. My reservation sits on the read side. One kind 3 is a single self-contained event. A follow set spread over hundreds of events only reconstructs if a client can pull the whole set from somewhere. No relay promises that. Whoever syncs against a relay that answers halfway computes a different list and never learns it. So keep the list computable, but let the per-follow events carry enough causal metadata to prove completeness before merging.
1 replies ↓
Technical Debt's avatar
Technical Debt technicaldebt@poster.place 2 weeks ago
This is completely wrong. There is no “last writer wins” in CRDTs, you’ve got to give up that CRUD mentality. Stuffing all your followings into a single “follow list” event is the problem. CRDT fixes that because it persists a history of intents. Imagine you are dealing with a monotonically increasing counter. You have two options to derive that counter: A. Emit a state event with the current count every time it increases B. Emit a increase counter event then derive the counter state by adding all the events There is not enough context with A to converge into an unambiguous state automatically, that is why clients like Nostur have to ask what you want to do when they detect something “strange” happened. It is also the reason why keeping an history of follow lists is a pointless exercise.
1 replies ↓
Roger's avatar
Roger roger@nostrcheck.me 2 weeks ago
LWW-Register is in the CRDT literature - Shapiro's taxonomy has it as the standard state-based register, so kind 3 technically is one. Definitional quibble, and your real point survives it: what it converges to is a value nobody chose. A single replaceable event cannot say "I dropped X" as distinct from "I never had X", so two writers merge deterministically into a list neither of them actually wrote. Which makes the rest of your argument right for a reason other than the one you gave. Option A is not ambiguous - it is perfectly determined, newest created_at wins, id breaks the tie. It just merges into a state that is not the sum of anyone's intent. That is what Nostur is reacting to: the client is not resolving a conflict, it is noticing that the state it now holds cannot be explained by any single action a human took. And yes, keeping a history of follow lists is pointless - not because history is bad, but because a state event is the wrong unit for it. After the fact you cannot separate a deliberate unfollow from a writer that started from a stale copy. Ops are the right unit, exactly like your B. The question is mostly hypothetical anyway: relays store only the newest version of a replaceable event, so unless somebody archives them there is no history left to keep.
1 replies ↓
Roger's avatar
Roger roger@nostrcheck.me 2 weeks ago
Skip the labels and take the counterexample itself. A does converge: highest created_at wins, id breaks a tie, every client lands on the same list. What it cannot do is keep the follow you added on the phone while it was offline, so everybody converges on a list nobody wrote. That dialog in Nostur is the client noticing the list in front of you no longer matches anything you did. There is no conflict left to resolve at that point. So the defect is agreed. The difference is the bill for B. Ops make every new client walk the whole op history, and "all ops" has no ceiling on a network where relays keep what they like and drop the rest. A state event is a single fetch and the answer is complete. Where B really wins is the part I gave away too cheaply. After the fact, a removal and a never-had look identical, so that information is destroyed when you write it, before any merge happens. Migration is the hard part. Most relays have already dropped the history, so B starts from a snapshot plus ops from some agreed date, and every client has to agree on that date.
1 replies ↓
↑