What you'll learn: By the end of this lesson you will be able to define strong eventual consistency, compare state-based and operation-based delivery, choose a conflict policy for a kind of data, explain how a sequence CRDT orders concurrent inserts with unique ids and tombstones, name its costs and limits, and run a TypeScript lab that shows each of them.
A shopping list is taped to the fridge, and a photo of it sits on every phone in the family. In a lift with no signal, one person crosses out "eggs" and another writes "bread" under "milk". Back online the phones must agree. "The later save replaces the list" loses an edit. "Line 3 means line 3" misplaces the new item, because lines shift as people edit. A conflict-free replicated data type (CRDT) has the rules for combining concurrent edits built into its definition, so every replica that has received the same edits shows the same list, whatever the order of arrival.
The small types (counters, last-writer-wins register, observed-remove set) and the three merge laws are in Idempotent and Commutative Operations; ordering tools are in Logical and Vector Clocks. This lesson covers delivery styles, conflict policy and the hard case, the ordered list.
Verified against Shapiro et al. (INRIA RR-7687, 2011) and Almeida's survey (arXiv 2310.18220, version 2), read on 2026-11-08. Lab run on Node 26.12.1 with Vitest 5.1.0.
The core idea
A CRDT makes convergence a property of the data type, so replicas accept writes locally, without coordination, and still end in the same state. Shapiro and colleagues call this strong eventual consistency (Definition 2.3): updates reach every correct replica, and correct replicas that have delivered the same updates have equivalent state. They contrast it with systems that apply an update, find the conflict later and roll back, which in general needs consensus so all replicas arbitrate alike.
SEC says every replica reaches the same answer, not that it is the answer a user meant. Choosing the answer is the design work.
Three illustrations, each labelled: a minimal example (two authors typing into one list, in "Build it"), a realistic example (a shared household list in ShopStream) and failure examples (interleaved typing, a reused replica id).
Two ways to carry the same update
In state-based designs replicas send state and the receiver merges. If states form a join-semilattice (any two have a least upper bound), merge computes that bound and updates only move state upward, replicas converge given eventual delivery (Theorem 2.1). In operation-based designs replicas send operations. Convergence assumes causal delivery (each message reaches every recipient exactly once, in an order consistent with happened-before) and that concurrent updates commute (Theorem 2.2). The authors state such a broadcast needs no consensus and may deliver concurrent updates in any order. Either style can emulate the other (Theorems 3.1 and 3.2).
Figure 1. The same update, carried two ways. How to read this: the top half sends one edit and puts the burden on delivery (order, no duplicates). The bottom half sends knowledge and puts the burden on the merge function, which is why it survives a lossy network.
| Question | Operation-based | State-based |
|---|---|---|
| Network needs | Reliable, usually causal delivery; exactly once for non-idempotent operations | None: tolerates loss, duplication, reordering |
| Participants | A known group; merging two independent groups is hard | Unknown or changing; groups can merge |
| Long partition or offline | Undelivered messages must be buffered, growing with the partition | Each replica is autonomous |
| Message size | Small | Larger, unless only the missing part is sent |
Almeida (section 7) gives this comparison, and adds that "CRDTs are types with commutative operations" is a misconception: the operation-based model exists to handle non-commutative operations such as a set's add and remove, with a side-effect-free prepare at the source and an effect designed to commute for concurrent operations.
Conflict resolution is a choice of meaning
For a concurrent add and remove of one element, Shapiro et al. list several options (add wins, remove wins, the highest replica address wins) and note every one satisfies strong convergence. The type fixes the choice, so it must match what the data means.
| Kind of data | Policy | Cost |
|---|---|---|
| A profile field | Last writer wins on (timestamp, replica id) | One concurrent write is silently dropped |
| A set (cart, tags) | Add wins: a remove cancels only the adds it saw | A remove can lose to a concurrent add |
| Both writes matter | Multi-value register: keep the concurrent values, let the reader choose | Readers handle several values |
| Ordered list or text | Sequence CRDT with unique element ids | Metadata, tombstones, interleaving |
| A limit (stock, balance floor, seat) | Not a CRDT job: coordinate | Refusal or waiting in a partition |
The last row follows from the definition. A CRDT operation never waits for other replicas (Almeida, section 2.4), so no replica can know another just took the last unit. Two replicas that each decrement a counter at zero both succeed and merge to minus one; the crdt-basics lab README describes this for its PN-counter. The CAP lesson puts money and uniqueness on the strict path.
Figure 2. A decision per field. How to read this: start at the top for each field of your model, not for the whole system. One product usually uses several branches.
Why a list is harder than a counter
A list has positions, and positions shift when anyone inserts before them. Operational transformation (OT) rewrites a remote operation's index before applying it. Almeida says it is manageable under central coordination (his example is Google Docs) and dauntingly complex for peer-to-peer replication, where early transformation functions were later found to violate their own correctness properties.
The CRDT answer is to stop using indexes. Each element gets a globally unique, immutable id and an operation says "insert after the element with this id". Designs like Treedoc, Logoot and LSEQ generate an id between neighbours, and ids grow. Designs like RGA, Woot and YATA use small ids, a pair (replica, counter) that Almeida calls a dot, plus ordering rules, and a delete leaves a tombstone. Per the survey, Automerge is based on RGA and Yjs on a modified YATA. The lab implements an RGA-style rule:
// from src/opReplica.ts, #integrate(): start just after the element this insert follows,
// then skip every node with a greater id; ids are (counter, replica name), counter first
while (i < this.#nodes.length && compareIds(this.#nodes[i]!.id, op.id) > 0) i++;A new element's counter exceeds every counter its author has seen, so it outranks the element it follows. Two inserts after one element are concurrent, and the greater id goes first on every replica. That rule is the whole policy for concurrent inserts. The state-based version of the lab reaches the same order differently: it walks the tree of "inserted after" links, children greatest id first.
Figure 3. The lab's first scenario. How to read this: the three edits are concurrent. The delete keeps 1@a as a tombstone, so the two inserts that follow it still have an anchor. Greater id first puts X (3@b) before b (3@a), then the older c (2@a).
Build it
Goal. Run both delivery styles on one list type and see convergence under shuffled and repeated deliveries, then the costs.
Setup. examples/frontend/labs/rga-replicated-list (pure TypeScript, seeded randomness), a sibling of examples/frontend/labs/crdt-basics (counters, register, OR-set). From the package folder:
pnpm test # 22 tests
node src/demo.ts # six scenarios, deterministic outputHow it works. OpReplica holds an array of nodes, applies the rule above and buffers operations whose anchor has not arrived. StateReplica holds two grow-only sets (all inserts, all deleted ids), merges by union and computes the text from the tree. The tests run 150 seeded sessions: operation-based replicas end identical with an empty buffer, the state-based replica gets the same text from the same operations in any order, union is commutative, associative and idempotent, and the two replica types agree.
Output of node src/demo.ts, captured on Node 26.12.1 (2026-11-08):
=== 1. Three replicas share the list "ac", then edit at the same time
shared start: a="ac" b="ac" c="ac"
a: insert 'b' as 3@a after 1@a -> a sees "abc"
b: insert 'X' as 3@b after 1@a -> b sees "aXc"
c: delete 1@a -> c sees "c"
now each replica receives the other two operations, in a different order each:
a receives delete 1@a -> applied, text "bc"
a receives insert 'X' as 3@b after 1@a -> applied, text "Xbc"
b receives insert 'b' as 3@a after 1@a -> applied, text "aXbc"
b receives delete 1@a -> applied, text "Xbc"
c receives insert 'X' as 3@b after 1@a -> applied, text "Xc"
c receives insert 'b' as 3@a after 1@a -> applied, text "Xbc"
converged: true (all three show "Xbc"; each keeps 4 nodes, 1 of them a tombstone)
=== 2. Operations that arrive before the element they refer to
a typed insert 'x' as 1@a after start, then insert 'y' as 2@a after 1@a; the network delivers y first
with a buffer : receive y -> buffered (waiting 1), receive x -> applied (waiting 0), text "xy"
without a buffer: receive y -> dropped, receive x -> applied, text "x"; a shows "xy"
=== 3. The same operations as state: set union, any order, no buffer
applied in issue order : "Xbc" (4 inserts, 1 tombstone)
applied in reverse order : "Xbc" (4 inserts, 1 tombstone)
every operation sent twice: "Xbc" (4 inserts, 1 tombstone)
first three operations alone "abc"; the other three alone "" (they follow an element that half does not hold, so nothing is reachable yet)
merge(h1,h2) -> "Xbc"; merge(h2,h1,h1) -> "Xbc"; same state: true
=== 4. 100 random sessions (seeds 1 to 100): 3 replicas, 60 steps, shuffled and repeated deliveries
operations issued: 3220; deliveries that had to wait for an element: 1578; repeated deliveries: 587; most operations any replica held back at once: 14
operation-based replicas ended identical and with nothing waiting: 100 of 100
state-based replica fed the same operations shuffled showed the same text: 100 of 100
replicas without a buffer: 100 of 100 sessions ended with different texts (1882 operations dropped in total)
=== 5. Two authors type at the same place: forwards, then backwards
forwards : a typed "ABC", b typed "123" -> a "X123ABC", b "X123ABC"
backwards: a typed "ABC", b typed "123" -> a "X1A2B3C", b "X1A2B3C"
=== 6. Tombstones: deleting does not free memory, and freeing it early is unsafe
typed 40 characters, deleted 30: visible 10, nodes kept 40, tombstones 30
both replicas hold the tombstone for 'a'; b's insert of 'b' after it is still in flight: a "c", b "bc"
a purges the tombstone (1 node freed), then the in-flight insert arrives -> buffered
a "c" but b "bc"; operations a is still holding back: 1Section 1 is Figure 3 for real: intermediate texts differ (aXbc, Xc), the end state does not. In section 2 an early operation must wait; without the buffer it is lost. Section 3 needs no buffer, at the price of keeping every insert and tombstone. In section 4, 1,578 deliveries of 3,220 operations had to wait and 587 were repeats; every session converged, and replicas with no buffer diverged in all 100. Section 5 is the interleaving anomaly, section 6 the tombstone cost.
Break it. In src/opReplica.ts comment out the skip loop. Six tests fail (concurrent inserts, both typing tests, 150-session convergence, five replicas, agreement with the state-based replica) because each replica now orders concurrent inserts by arrival. Then reverse the child sort in src/stateReplica.ts: one test fails, since the two replica types now disagree. Both were run.
Stretch. Track a version vector and purge a tombstone only when its delete is causally stable. Add a delta mode that sends only what the other side lacks.
What the model leaves out. One id per character, linear anchor search, no formatting or moves, no network, no authorization, and no line-by-line check against published RGA pseudo-code.
Tombstones, metadata and garbage collection
Almeida notes tombstones make state grow without bound, and removing one safely relies on causal stability: a message is stable at a replica when every message delivered afterwards will be causally after it, so no concurrent operation referring to it can still arrive. That is stronger than "every replica has the delete", as demo section 6 shows. For pure operation-based designs he notes operations stop becoming stable during a partition, which costs memory, not availability. Causal CRDTs keep a dot store and a causal context instead of tombstones. Identity costs too: Almeida calls the growth of replica-id maps the main obstacle to scaling CRDTs to many participants.
Two ways it goes wrong
Interleaving. Almeida quotes an example from Kleppmann et al.: two users insert " Alice" and " Charlie" at one place in "Hello!" and many sequence CRDTs converge on "Hello Al Ciharcliee!". He reports it in Logoot, LSEQ, Treedoc and Woot, a lesser form in RGA when typing backwards, and a CRDT (Fugue) built to avoid it. The lab reproduces the RGA case: X1A2B3C. Convergence is the easy part; defining the intended outcome is hard.
Reused ids. Uniqueness is assumed everywhere. In a throwaway script against the lab, a replica a restored from an old backup typed y as 1@a while b already held x as 1@a. b treated it as a duplicate and ignored it: a showed y, b showed x, and nothing repairs it. The fix is outside the CRDT: a restore always gets a new replica id.
The other side of this topic
On the client this is local-first editing and offline queues. The Frontend System Design track plans a lesson on CRDTs and operational transformation (not published yet, so no link).
In practice: a shared household list in ShopStream
This is the realistic example, an educational scenario on ShopStream. Nothing in it describes a real company, and the feature and every figure are illustrative.
This is a realistic scenario, not a case history.
The situation
ShopStream wants a shared list: a household keeps one ordered shopping list edited from several phones, including in a shop with weak signal. The first prototype saves the whole list as one document on each change, so two members editing at once overwrite each other.
Starting architecture
Figure 4. The shared-list design. How to read this: phones apply edits at once and send operations in the background. The sync service authenticates, stores and relays; it does not edit. Anything with a limit goes to checkout, which re-checks it.
Options considered
| Option | Behaviour | Cost | Risk |
|---|---|---|---|
| A. Whole-document last writer wins | Simple | One writer's edits vanish | Lost items |
| B. Server assigns every edit its place (central OT style) | Predictable | Edits wait for the server; offline is hard | Server in every edit |
| C. Sequence CRDT per list, relayed by the server | Local, offline friendly | Metadata, tombstones, delivery layer | Interleaving, untrusted operations |
The decision
Option C for the list, strict handling for limits. The list holds names and notes, where a merged outcome is fine. "Send to cart" copies items into the cart and re-validates stock and price at checkout, since a CRDT cannot know the last unit is gone. The sync service checks that the sender may edit, validates each operation's shape (a forged operation would merge like any other), and issues every install and every restore a fresh replica id. "Clear list" starts a new list instead of deleting items one by one, which bounds tombstones.
Rollout and verification
Run the new lists beside the old documents for a few households and compare. Verification mirrors the lab: shuffled and repeated operation order ends identical, and replaying the stored log rebuilds the same list. Metrics: buffered operations, nodes against visible items, sync lag.
The 2 a.m. failure
Support reports a list two family members see differently. Check operation counts and highest counters per replica id, and look for one replica id on two devices. The cause here is a phone restored from backup with its old id, so its new items reused ids and were ignored as duplicates. Mitigation: issue a new id, rebuild the phone's view from the store, re-enter the lost items. Lasting fix: a restore always means a new replica id.
Architect's notes
- Write the merge meaning per field before choosing a library.
- Keep limits off the CRDT: stock, balances and uniqueness need one authority and a re-check.
- Treat operations as untrusted input: authorize and validate before relaying.
- Plan metadata: track nodes against visible items and decide how tombstones are reclaimed.
- Offline-heavy clients suit state-based or delta propagation; known, well-connected groups suit operation-based (Almeida's summary).
Common mistakes
- Assuming a CRDT decides what a conflict means. It guarantees agreement, not intent.
- A CRDT counter for a limited resource. Both replicas can spend the last unit.
- Dropping operations that arrive early. Hold them, or use state-based delivery.
- Purging tombstones because every replica has them. An operation in flight can still refer to one.
- Reusing a replica id, or using indexes in operations.
Key takeaways
- A CRDT guarantees strong eventual consistency without coordination.
- State-based merge tolerates loss, repeats and reordering; operation-based delivery needs reliable, usually causal delivery.
- Every conflict policy converges; pick the one that matches the data.
- Lists use unique element ids and tombstones, not indexes.
- Tombstone removal needs causal stability.
- Convergence does not prevent interleaving, and a CRDT cannot enforce a limit.
Practice exercises
Exercise 1 (30 min). For each demo section, name the theorem or assumption (eventual delivery, causal delivery, commutativity, union as least upper bound) it illustrates.
Exercise 2 (45 min). For five fields of a food-delivery app (driver status, order notes, favourites, wallet balance, delivery checklist) pick a policy from Figure 2 and say what is lost.
Exercise 3 (1 hour). Run both "Break it" experiments and write which assumption each removed.
Exercise 4 (2 hours). Add delta(since) to StateReplica and show merging only deltas converges on the seeded sessions.
Exercise 5 (2 hours). Design the tombstone-reclaim rule for the household list, including a phone offline for a month.
Related reading
- Idempotent and Commutative Operations: the three laws, counters and the observed-remove set.
- Logical and Vector Clocks: happened-before and version vectors.
- Consistency Models: where eventual and causal consistency sit.
- CAP Theorem and PACELC: why availability needs a merge rule.
- Labs:
examples/frontend/labs/crdt-basicsandexamples/frontend/labs/rga-replicated-list.
Official documentation
- Shapiro, Preguica, Baquero and Zawirski, Conflict-free Replicated Data Types, INRIA RR-7687 (2011): SEC and the state-based and operation-based theorems.
- Almeida, Approaches to Conflict-free Replicated Data Types (arXiv 2310.18220, version 2): the survey behind the comparison, sequence CRDTs and anomalies.
- Shapiro, Preguica, Baquero and Zawirski, A comprehensive study of Convergent and Commutative Replicated Data Types, INRIA RR-7506 (2011): the longer companion study.