CRDTs & Conflict Resolution

Module promise

This module should take a learner from “I have heard that CRDTs magically merge stuff” to “I can build and test the CRDT core of a small collaborative editor.”

The point is not to memorize names like G-Counter, OR-Set, or MV-Register. The point is to internalize the few hard ideas that keep reappearing:

• state may arrive late;
• messages may be duplicated;
• two users may make valid changes without seeing each other;
• a server may help deliver updates, but it should not be the place where meaning is invented;
• convergence is a property you design and test, not a wish.

The module is intentionally explicit. Some walkthroughs almost give away the solution. That is deliberate. In distributed systems, a vague hint often teaches the wrong lesson: the learner writes something that passes a toy case but fails under duplicate delivery or concurrent updates.

1. The pain: when “last write wins” destroys work

Imagine two people editing a shared note while temporarily offline.

Initial text:

Launch checklist

Replica A adds:

Launch checklist
- verify DNS

Replica B adds:

Launch checklist
- notify support

When they reconnect, a naive system might say: “B has the later timestamp, so B wins.”

Final text:

Launch checklist
- notify support

A’s valid work disappeared. That is not conflict resolution. That is conflict deletion.

A different naive system might concatenate states, but then duplicates appear after retry. Another might try to replay positions, but “insert at index 17” stops meaning the same thing once another user inserts text before that index.

CRDTs attack the problem differently. They do not ask: “Which replica wins?” They ask: “What information do we need to preserve enough intent, and what deterministic rule makes all replicas reach the same answer?”

2. CRDTs in one sentence

A Conflict-free Replicated Data Type is a data type designed so replicas can update locally and later merge or exchange operations while still converging to the same logical value.

There are two common styles:

State-based CRDTs send state and merge it with a join operation.

Operation-based CRDTs send operations. They still need idempotence, causal handling, or unique operation IDs so duplicate and reordered delivery do not corrupt the result.

This module teaches both, but the capstone uses an operation-based sequence CRDT because text editing is naturally operation-shaped: insert this character after that character; delete that known character.

3. The three merge laws

For state-based CRDTs, the merge operation must behave like a mathematical join. The usual laws are:

commutative:  merge(a, b) = merge(b, a)
associative:  merge(a, merge(b, c)) = merge(merge(a, b), c)
idempotent:   merge(a, a) = a

These laws are not academic decoration.

Commutativity means delivery order does not matter.

Associativity means batching does not matter. A replica can merge A then B, or merge a bundle containing A and B.

Idempotence means duplicate delivery does not matter. If the same state arrives twice, nothing is counted twice.

A learner should test these laws directly. The first standalone problem does exactly that.

4. G-Counter: the first useful trick

A normal integer counter is not safe under naive merge.

Replica A increments from 0 to 1. Replica B increments from 0 to 1.

If the merge rule is “take max integer,” the final value is 1. But two increments happened. The correct final value is 2.

A G-Counter stores one slot per replica:

A sees: [1, 0]
B sees: [0, 1]
merge:  [1, 1]
value:  2

The merge rule is element-wise max. The value is the sum.

Why max? Because a replica’s own slot only grows. If A’s slot is 5 in one state and 3 in another, 5 contains all updates represented by 3 and more. Max is the least state that includes both.

The hidden lesson: CRDT design often means keeping more metadata than the final user-facing value.

5. PN-Counter: subtraction without unsafe subtraction

A PN-Counter supports increments and decrements by using two G-Counters:

P = increments per replica
N = decrements per replica
value = sum(P) - sum(N)

Merge both vectors by element-wise max.

Do not store only the final integer. The final integer loses causal information. Two users can both decrement from 10 to 9, but that does not mean only one decrement happened.

6. LWW Register: useful, dangerous, and often overused

A Last-Write-Wins register stores:

value
timestamp or logical clock
tie-breaker

The value with the larger timestamp wins. If timestamps tie, a deterministic tie-breaker wins.

This is a CRDT if the ordering is total and deterministic. But it may be a bad product decision because it discards concurrent values.

Use LWW when overwriting is truly acceptable:

• cursor color;
• user display name;
• transient preference;
• cached latest status.

Avoid LWW when lost work matters:

• document body;
• comments;
• shopping cart quantities;
• financial ledger entries.

One important correction: if timestamp and node ID are equal but values differ, returning the left argument is not commutative. A serious implementation must either make such states impossible or add a final deterministic tie-breaker over the value.

7. Vector clocks: “before”, “after”, and “concurrent”

A vector clock records how many events from each replica are known.

Example with two replicas:

[2, 0] means: I know two events from replica 0 and zero from replica 1.
[1, 3] means: I know one event from replica 0 and three from replica 1.

Comparison:

A <= B if every component of A is <= the corresponding component of B.
A <  B if A <= B and at least one component is strictly smaller.

If neither clock dominates the other, the events are concurrent.

[2, 0] and [1, 3] are concurrent

Vector clocks are not “timestamps with arrays.” They answer a different question: not “which happened later on the wall clock?” but “could this event have observed that event?”

8. MV-Register: preserve concurrent writes

A Multi-Value Register keeps all values that are not causally dominated.

Suppose:

A writes title = "Draft"       clock [1,0]
B writes title = "Proposal"    clock [0,1]

Neither write observed the other. The MV-Register returns both values. The application can show a conflict UI:

This field has concurrent values:
- Draft
- Proposal
Choose one or combine them.

If A later sees B’s value and writes “Draft Proposal” at clock [2,1], that clock dominates both earlier versions, so the register contains one value again.

MV-Register is a better teaching example than LWW because it shows what “do not lose work” means.

9. OR-Set: remove only what you observed

A set seems easy until add and remove happen concurrently.

Start with empty set.

A adds milk. B, without seeing A’s add, removes milk.

Should milk be present?

In an Observed-Remove Set, an add creates a unique tag:

add milk with tag A#1

A remove records the tags it has observed. If B has not seen A#1, B cannot remove it. So after merge, milk remains.

This sounds strange until you map it to user intent. B did not remove A’s item. B removed the versions of milk B had seen.

10. OR-Map and shopping carts

Real applications need nested data.

A shopping cart can be modeled as:

OR-Map<ProductID, PN-Counter>

The OR-Map tracks which product keys exist. The PN-Counter tracks quantity. Concurrent increments merge. Removals must be designed carefully.

This module includes a shopping-cart problem because it forces the learner to compose CRDTs instead of treating them as isolated toys.

11. Text editing is harder than counters

A collaborative editor cannot safely use “insert at index 5” as a permanent operation. Indexes shift.

Initial:

abc

A inserts X at index 1:

aXbc

B inserts Y at index 1 concurrently:

aYbc

When operations meet, both were valid. If both say “insert at index 1,” the final order depends on delivery order unless we add more structure.

Sequence CRDTs solve this by giving each inserted character a stable ID and expressing insertion relative to another ID:

insert X after char a, id A#1
insert Y after char a, id B#1

Now both operations refer to the same stable parent. The CRDT only needs a deterministic rule for ordering siblings inserted after the same parent.

The capstone uses a simplified RGA-style sequence CRDT:

• each character has an ID (actor, sequence);
• each insert says after: parentID;
• deletes create tombstones instead of removing the node;
• rendering walks the tree from the root;
• siblings are sorted deterministically by ID.

This is not a complete Google Docs clone. It is a deliberately small system that exposes the real mechanics.

12. Tombstones: ugly but important

If you physically remove a character, later operations that refer to it may lose their anchor.

Example:

A inserts X after B
C deletes B

If B disappears completely, where should X go? A sequence CRDT keeps B as a tombstone: invisible to the user, still useful as a position anchor.

This is a major “professional” lesson. Many CRDT explanations hide tombstones because they are inconvenient. Real systems must deal with them using compaction, snapshots, causal stability, or more advanced structures.

13. Operation logs and sync

The capstone server is not the source of truth for meaning. It is a delivery and storage helper.

A useful sync protocol needs:

• unique operation IDs;
• idempotent apply;
• a version vector so clients can ask for missing operations;
• snapshots so new clients do not replay an infinite log;
• deterministic render so all clients display the same text.

The included scaffold starts with HTTP polling because it keeps networking simple. Learners can upgrade to Server-Sent Events or WebSockets as an extension. The CRDT core does not depend on the transport.

14. What the capstone asks the learner to build

The provided code includes:

• a Go HTTP server;
• a browser UI;
• a textarea-to-operation adapter;
• document endpoints;
• an in-memory operation store;
• tests;
• a complete reference implementation.

The learner implements:

• operation identity and idempotence;
• insert application;
• delete tombstones;
• deterministic rendering;
• visible character extraction for the UI;
• version-vector calculation;
• missing-operation selection;
• merge/convergence tests;
• conflict inspection extensions.

The final experience should be:

1. Run two browser tabs with different replica IDs.
2. Type in both tabs.
3. Disable syncing or edit quickly to create concurrent inserts.
4. Re-enable sync.
5. Both tabs converge to the same text.
6. Duplicate POSTs or repeated polling do not duplicate text.

15. A professional testing mindset

A CRDT that passes one example is not done.

Test these properties:

• Applying the same operation twice has the same result as applying it once.
• Applying operations in different orders converges if dependencies are eventually present.
• Concurrent inserts after the same parent have deterministic order.
• Delete-before-insert is handled by tombstone memory.
• Rendering does not depend on Go map iteration order.
• Missing-op queries do not resend operations a peer already has.
• Snapshots and logs agree.

You should make learners uncomfortable with “it works on the happy path.” CRDTs fail in the unhappy path.

16. What this module does not pretend

The capstone is not production Google Docs.

It does not solve:

• rich-text mark intent preservation;
• undo/redo semantics;
• garbage collection of tombstones;
• large-document indexing;
• access control;
• encrypted sync;
• cursor presence;
• operational transform;
• production persistence.

Those are excellent extension tracks. But the learner first needs to understand the core loop: local operation, stable identity, idempotent apply, deterministic render, missing-op sync, convergence.