How to Learn Conflict-Free Replicated Data Type (CRDT) Algorithms: State Merges, Concurrent Updates, OR-Sets and Convergence

Wait, What?

Two people can change the same data while disconnected, reconnect later, and still end with the same answer—without asking a central server to choose a winner.

That sounds impossible until the data structure itself is designed for concurrency. Conflict-Free Replicated Data Types, usually called CRDTs, are replicated data structures whose update and merge rules are constructed so that independently updated copies can converge deterministically.

This is not a magic replacement for every consistency problem. CRDTs solve a specific job: they make certain kinds of concurrent updates mergeable without coordination. The learning challenge is to understand exactly which algebraic guarantees make that possible, what metadata those guarantees cost, and when a CRDT is the wrong tool.

Quick Answer

Learn CRDTs through the route replicas → concurrent updates → convergence goal → commutative/idempotent merge → grow-only counter → grow-only set → state-based CRDT → operation-based CRDT → causal order → observed-remove set → tombstones and metadata → delta-state CRDT → collaborative sequences → testing under reorder/duplication/partition → production trade-offs. A beginner should be able to merge a counter or set by hand. A professional should be able to state the convergence assumptions, choose an appropriate CRDT family, test pathological message schedules, and explain the metadata and semantics of deletes.

1. Start With Replication, Not With Acronyms

Suppose the same logical object exists on two devices, A and B. Each device may update its local copy before it hears from the other. When communication resumes, the system must combine those histories.

The core difficulty is not copying data. It is deciding what concurrent changes mean.

2. Concurrency Means Neither Update Is Clearly Before the Other

If A updates first and B definitely sees that update before writing, there is a causal order. But if A and B update while disconnected, neither operation may have observed the other. Those operations are concurrent.

The existing How to Learn Distributed Algorithms article owns the wider world of logical clocks, consensus and failure models. This article owns the narrower CRDT job: how a replicated data type itself can make concurrent state merge safely.

3. The Target Guarantee Is Strong Eventual Consistency

A useful CRDT target is that replicas which have incorporated the same updates end in equivalent states. The CRDT community commonly describes this as strong eventual consistency. The CRDT resource site provides an accessible overview and links to the foundational literature.

4. Begin With a Grow-Only Counter

A first exercise is a counter that can only increment. Give every replica its own component. Replica A increments A’s component; replica B increments B’s component. The logical value is the sum of all components.

To merge two states, take the component-wise maximum. If one message is duplicated or arrives late, the maximum operation does not double-count it.

5. Why the Merge Laws Matter

• Commutative: merge(A,B) gives the same state as merge(B,A).
• Associative: grouping merges differently does not change the result.
• Idempotent: merging the same state twice does not keep changing the result.

These laws make state-based propagation tolerant of reordering and duplication. They are not decorative algebra. They are what make unreliable delivery schedules manageable.

6. Grow-Only Sets Make the Same Pattern Visible

A grow-only set adds elements but never removes them. Two replicas merge by set union. Union is commutative, associative and idempotent, so all replicas converge after they have received the same additions.

7. State-Based CRDTs Merge States

State-based CRDTs, often called CvRDTs, exchange replica state and merge those states. Their merge operation is typically defined as a least upper bound in a join-semilattice, and updates move state monotonically upward in that ordering.

Do not rush past the word monotonic. It means the internal information used to establish convergence only accumulates according to the CRDT’s order, even if the user-facing value appears to shrink after a logical remove.

8. Operation-Based CRDTs Send Operations Instead

Operation-based CRDTs, often called CmRDTs, distribute operations rather than entire states. Their convergence conditions rely on the operations that can be concurrent commuting with one another, together with appropriate delivery guarantees.

The key lesson is that bandwidth and network assumptions trade against each other. Smaller messages do not automatically mean a simpler system.

9. A Remove Operation Is Where the Easy Story Breaks

Adding to a grow-only set is monotonic. Removing is harder. If A removes item X while B concurrently adds X, what should happen?

There is no universally correct answer. The data type must define one. Some sets are add-wins; some are remove-wins; some model the problem differently.

10. The Observed-Remove Set Teaches Precise Delete Semantics

In an observed-remove set, an add is associated with a unique event or tag. A remove removes the additions it has actually observed. A truly concurrent unseen add can therefore survive.

This is much more precise than saying “add wins.” The learner should be able to explain why the concurrent add survives: the remove had no evidence of that add to remove.

11. Tombstones Solve One Problem and Create Another

A naïve replicated set may remember deleted event identifiers forever so that an old message cannot resurrect removed data. These remembered deletions are often called tombstones.

Tombstones help correctness but can make metadata grow without bound. More advanced OR-Set designs use causal context and compact version information to reduce this cost.

12. Causal Context Is Part of the Data Structure’s Memory

Version vectors, dots and related causal metadata let a replica distinguish an event it has observed from one that is genuinely concurrent. That distinction is central to safe removal and compacting old history.

13. Delta-State CRDTs Reduce Synchronisation Cost

Full-state exchange can be expensive for large objects. Delta-state CRDTs produce small states representing recent changes and join those deltas into replica state. Almeida, Shoker and Baquero’s Delta State Replicated Data Types develops this model and its anti-entropy requirements.

Current Apache Pekko Distributed Data documentation is a useful production-facing example: delta propagation reduces traffic, while causal delivery requirements still matter for some data types.

14. CRDTs Do Not Eliminate Semantics

A merge can be mathematically convergent and still be wrong for the product. A shopping cart, bank balance, collaborative text document and permission list do not share the same conflict semantics.

The professional question is never just “Can I use a CRDT?” It is “Does this CRDT’s merge meaning match the domain invariant?”

15. Collaborative Sequences Are Much Harder Than Sets

Text editing requires concurrent insertions and deletions at positions whose meaning may shift as other edits arrive. Practical sequence CRDTs therefore identify logical positions or elements in ways that survive concurrent editing.

Modern libraries demonstrate how far this field has developed. Automerge supports local updates that later synchronise and merge, while Yjs exposes shared CRDT-backed types for collaborative applications.

16. Production Libraries Hide Complexity—but Not Trade-Offs

A library may handle event identifiers, causal history, compaction and sync protocols for you. You still need to understand memory growth, conflict semantics, offline duration, object size, garbage collection and whether the chosen model preserves your application’s invariants.

Redis Enterprise’s Active-Active documentation is one current example of CRDTs used for geo-distributed active-active data.

17. Test the Network, Not Just the Happy Path

A CRDT implementation should be tested under permutations of message schedules:

• messages delivered in different orders;
• duplicate messages;
• long partitions followed by reconnection;
• concurrent add/remove pairs;
• replica restart from persisted state;
• partial sync followed by more local edits;
• many replicas updating the same key;
• metadata compaction after causal stability.

18. Property-Based Testing Fits CRDTs Naturally

Generate random operations, distribute them across replicas, randomise message order and duplication, and assert that replicas converge after all relevant updates are delivered. This tests the guarantee against far more schedules than a handful of hand-written examples.

19. Separate Convergence From Application Correctness

Replica convergence answers one question: did the copies end in the same state? Application correctness asks another: is that state allowed?

A convergent counter can still violate an inventory floor. A convergent set can still grant a permission that required coordination. Some invariants fundamentally require coordination or stronger transactional guarantees.

20. Formal Verification Shows the Standard of Proof

The Archive of Formal Proofs CRDT framework mechanises strong eventual consistency reasoning for concrete CRDTs such as counters, OR-Sets and replicated growable arrays. Professionals need not formally verify every application, but the existence of machine-checked proofs is a reminder that convergence is a theorem with assumptions, not a slogan.

21. Common Learning Failure States

• Equating eventual consistency with strong eventual consistency.
• Assuming “last write wins” is automatically a CRDT.
• Memorising commutative/associative/idempotent without connecting them to message reorder and duplication.
• Thinking all CRDTs can delete without metadata.
• Calling every concurrent edit a conflict that needs a human.
• Assuming convergence guarantees a valid business state.
• Ignoring causal delivery assumptions for operation-based or delta designs.
• Benchmarking throughput while ignoring state and metadata growth.
• Using a sequence CRDT without testing long offline histories.
• Reimplementing a complex text CRDT when a mature library is the safer choice.

22. A Beginner-to-Professional Learning Ladder

• Level 1: merge two grow-only counters by hand.
• Level 2: explain why set union tolerates duplicate delivery.
• Level 3: distinguish state-based from operation-based CRDTs.
• Level 4: trace concurrent add/remove behaviour in an OR-Set.
• Level 5: explain causal context and why deletes need history.
• Level 6: implement a small counter or set CRDT.
• Level 7: fuzz message order, duplication and partitions.
• Level 8: compare full-state and delta-state propagation.
• Level 9: evaluate a production library’s semantics and metadata costs.
• Level 10: decide which domain invariants can remain coordination-free and which cannot.

23. Teach the Need Before the Algebra

Give learners two offline replicas and ask them to predict the result of reconnecting after concurrent edits. Let a naïve merge fail first. Then introduce the algebraic properties that would make reordering and duplication harmless.

This predict-run-investigate progression aligns well with PRIMM, which moves learners from prediction and execution toward investigation, modification and independent construction.

24. Use Faded Worked Examples for Causal Traces

Begin with a fully worked two-replica trace showing event identifiers and causal context. In the next example remove the merge result. Then remove the causal labels. Finally ask the learner to design and verify the merge independently.

Programming-education research on worked examples and metacognitive scaffolding found particularly strong outcomes when guidance was faded as learners gained control of the problem-solving process. See Shin et al. (2023).

25. Parsons Problems Work for Merge Logic

Instead of asking a novice to write an OR-Set from a blank file, provide shuffled steps for tag creation, causal observation, remove, merge and query. Learners reconstruct the logic before coding it.

An ICER 2024 study of Parsons problems found improved grades and learning efficiency for novices working on an integrated programming task.

26. Immediate, Delayed and Transfer Checks

• Immediate: merge two counter states.
• Concept: state the three key merge properties and what network fault each helps tolerate.
• Trace: resolve one concurrent OR-Set add/remove schedule.
• Delayed: explain state-based versus operation-based assumptions without notes.
• Transfer: choose between coordination, CRDT merge and ordinary single-writer storage for three application cases.
• Professional: construct randomized message schedules and verify convergence plus domain invariants.

Metacognitive prompts should stay inside the technical work: What has this replica actually observed? What operation is concurrent? Which invariant is guaranteed by the merge law? Which invariant is not? The EEF’s updated Metacognition and Self-Regulated Learning guidance emphasises planning, monitoring and evaluation embedded within subject learning.

27. AI Assistance Boundary

AI can generate replica traces, adversarial message schedules, state diagrams and test cases. The learner should still be able to state the CRDT’s merge rule, explain its convergence assumptions, trace concurrent operations and independently verify whether the final state respects the domain invariant.

Professional Direction

Advanced study includes join-semilattices, pure operation-based CRDTs, delta-mutators, dotted version vectors, causal stability, sequence CRDTs, JSON CRDTs, operation transformation comparisons, local-first software, anti-entropy protocols, Byzantine settings, formal verification, metadata compaction and invariant-confluence.

Algorithm-learning rule: when two replicas disagree, do not ask only how to make them equal. Ask what each replica has observed, which updates are concurrent, what merge laws guarantee, what metadata preserves that evidence, which application invariant must survive the merge, and whether the system can safely remain coordination-free.