CRDTs & Conflict Resolution

The problem

Two users edit offline. Both changes are valid. Network later reconnects. What should the system do?

Bad answer: choose one whole document and discard the other.

Goal

Build data types that allow local updates and later convergence.

Not magic. Not “eventual consistency” as a slogan. A concrete merge/apply design.

Merge laws

For state-based CRDTs:

• commutative
• associative
• idempotent

These mean order, batching, and duplicate delivery do not change the result.

G-Counter

Problem: max integer loses concurrent increments.

Solution:

• store one count per replica;
• merge by element-wise max;
• value is sum.

Metadata preserves intent.

PN-Counter

Two G-Counters:

• P for increments;
• N for decrements;
• value = sum(P) - sum(N).

Never merge only the final integer.

LWW Register

Higher timestamp wins. Tie-break deterministically.

Useful for low-value overwrites. Dangerous for user-created content.

Question: what work are we willing to lose?

Vector clocks

Wall clocks answer: what time did the machine say? Vector clocks answer: what did this event know?

Outcomes:

• before;
• after;
• equal;
• concurrent.

MV-Register

Keep all values that are not causally dominated.

This converts hidden data loss into visible conflict resolution.

OR-Set

Adds get unique tags. Removes remove observed tags only.

Concurrent add and remove can preserve the add.

OR-Map

Real structures compose CRDTs.

Example:

ShoppingCart = OR-Map<ProductID, PN-Counter>

Text editing problem

Indexes are unstable.

“Insert at index 5” means different things after concurrent edits.

Use stable character IDs instead.

Sequence CRDT idea

Insert operation:

insert value V with id A#7 after parent B#3

Delete operation:

delete target A#7

Render deterministically.

Tombstones

Deleted characters stay as invisible anchors.

They preserve positions for operations that arrive later.

Sync protocol

Needed pieces:

• operation IDs;
• version vector;
• missing-op query;
• idempotent apply;
• snapshot;
• deterministic render.

Capstone

Build a collaborative browser editor.

Provided:

• Go HTTP server;
• browser UI;
• polling sync shell;
• textarea diff adapter;
• tests;
• reference solution.

Learner implements:

• CRDT document core;
• version vectors;
• missing-op sync;
• convergence behavior.

Final demo

Open two tabs. Type concurrently. Sync. Both converge. Duplicate delivery does not duplicate characters. Delete-before-insert still works.