CRDTs + Probability

CRDT merge semantics

Prerequisites

graph TD
  Prob[Probability basics] --> CRDT[CRDTs + Probability]
  Bloom[Bloom Filters] --> CRDT
  Dist[Distributed systems intuition] --> CRDT
  Gossip[Gossip / eventual consistency] --> CRDT

When to use

Offline-first collaboration — shared documents, shopping lists, or game state that must merge without a central lock.
Edge and mobile replicas — phones or IoT devices partition often; you need commutative, associative merge (join ⊔).
Massive scale where exact tombstones and vector clocks are too heavy — probabilistic Bloom tombstones and compressed clocks trade rare false positives for kilobytes of metadata.

When not to use

You need linearizable or strong consistency on every read (use Raft, primary-replica, or a central DB).
Every write must be preserved with zero chance of loss — probabilistic tombstones can false-positive and drop a valid stale update.
The domain is a simple counter on one machine — a SQL UPDATE or atomic integer is simpler than a CRDT lattice.

Lab

On the interactive CRDT lab, use G-Counter lattice to merge replica vectors with ⊔ (per-replica max) and compare against a naive sum after Partition heal. Try Concurrent increments or LWW conflict presets, predict whether merge matches naive sum, then reveal CRDT vs naive / LWW. Switch to Prob. tombstones for Bloom-backed deletes, Compaction demo, and a stale add after partition heal.

Simple Fundamental Explanation

Imagine you and your friend are both editing a shared grocery list on your phones, but you are both in a tunnel with no cell service.

You add “Apples”.
Your friend adds “Bananas”.

When you both drive out of the tunnel, your phones reconnect. How do they merge the lists without deleting one of the items? A CRDT (Conflict-free Replicated Data Type) is a mathematical data structure designed exactly for this. It guarantees that if two computers make changes offline, they can always merge those changes cleanly and automatically without a central server or human intervention.

However, standard CRDTs require storing a lot of metadata. To know exactly when and where to merge “Bananas”, the CRDT has to keep track of massive, complex history trees. If 1,000,000 people are editing a document, the metadata becomes larger than the document itself.

CRDTs + Probability solves this by accepting a tiny amount of uncertainty. Instead of storing the exact, perfect history of every keystroke, the system uses probabilistic structures (like Bloom Filters or hashing) to compress the history. When merging, it uses probability to guess the correct order or state. You might occasionally lose a single keystroke in a massive merge collision, but the memory usage drops from Gigabytes to Kilobytes.

Deep Dive: How It Works Under the Hood

The Standard CRDT Problem

To ensure strong eventual consistency, a standard CRDT (like a sequence or a set) must commute. If Node A applies operation X then Y, and Node B applies Y then X, they must reach the exact same state. To do this, CRDTs use Tombstones (when you delete an item, you don’t actually delete it; you just mark it as invisible) and Logical Clocks (Vector Clocks). As the system runs, the state grows monotonically. It never shrinks. Memory bloat is the #1 enemy of CRDTs.

The Probabilistic Optimization

To scale CRDTs to massive sizes, researchers introduce probabilistic boundaries.

Probabilistic Tombstones: Instead of keeping a permanent ID for every deleted item, the system throws deleted IDs into a Bloom Filter or Cuckoo Filter.
- When a delayed message arrives saying “Hey, modify item X”, the node checks the Bloom Filter.
- If the filter says “Item X is probably deleted”, the node ignores the modification.
- The Catch: A false positive means a valid, living item might accidentally be ignored.
Probabilistic Vector Clocks (Dotted Version Vectors): Standard vector clocks require $O (N)$ space, where $N$ is the number of active nodes. In a system with a million edge devices (mobile phones), this is impossible. Probabilistic clocks compress this history using hash-based sampling.

Visual Diagram: Probabilistic Deletion

Node A (Online)                       Node B (Offline for a week)

List: [Apple, Banana, Cherry]         List: [Apple, Banana, Cherry]

Node A deletes Banana.
Normally, A must keep "Banana (Tombstone)" forever in case B wakes up.

With Probabilistic CRDT:
A deletes Banana.
A adds hash("Banana") to a Bloom Filter.
A actually deletes Banana from memory.

Node B wakes up.
B says: "Update Banana to Green Banana!"

A checks Bloom Filter for hash("Banana").
Filter says: 1 (Probably deleted).
A rejects the update.
State safely converges without storing tombstones!

Practical Example: Massive Multiplayer Gaming

In a massive multiplayer online game, millions of players are moving around a map simultaneously.

If the game used a standard CRDT to track the position of every player, the metadata required to perfectly resolve the chronological order of every footstep would crash the servers. If the game used a central lock (Strong Consistency), the lag would make the game unplayable.

Instead, games use a hybrid. The state of the world is a CRDT (everyone can update their position locally without locking), but the conflict resolution is probabilistic. If Player A and Player B pick up the same gold coin at the exact same millisecond, the server doesn’t trace the perfect vector clock history. It probabilistically hashes their timestamps and client IDs, effectively flipping a coin to decide who gets the gold.

By applying probabilistic conflict resolution, the data structure remains mathematically guaranteed to converge, but the memory overhead of achieving that convergence is drastically reduced.

The Mathematics: Equations and In-Depth Analysis

1. Vector Clock Compression

A standard Vector Clock for $N$ nodes is an array of $N$ integers: $V = [c_{1}, c_{2}, \dots, c_{N}]$ . The memory footprint is $O (N)$ .

To compress this, we can use a Bloom Clock. Instead of an array of counts, a Bloom Clock is a bit array of size $M$ . When an event occurs at node $i$ with counter $c$ , we hash the string Node_i_Counter_c using $k$ hash functions and set those bits to 1.

To compare if Event A happened before Event B, we check if the Bloom Filter of A is a strict subset of the Bloom Filter of B.

Because it’s a Bloom Filter, there is a probability of a false positive (thinking A happened before B when they were actually concurrent). The false positive rate $P$ for comparing two Bloom Clocks is:

P \approx (1 - e^{- k n / M})^{k}

2. State-Based CRDT Convergence

A state-based CRDT is formally a join semi-lattice. The state space $S$ must have a partial order $\leq$ , and a merge function (least upper bound) $⊔$ . For all states $x, y, z$ :

Commutativity: $x ⊔ y = y ⊔ x$
Associativity: $(x ⊔ y) ⊔ z = x ⊔ (y ⊔ z)$
Idempotence: $x ⊔ x = x$

When we introduce probability (like replacing sets with Bloom Filters or HyperLogLogs), the merge function $⊔$ is usually a bitwise OR. If $B_{x}$ and $B_{y}$ are Bloom filters representing the sets, the merged state is simply $B_{x} \lor B_{y}$ . This operation perfectly satisfies commutativity, associativity, and idempotence. The underlying mathematical lattice of the CRDT is perfectly preserved, even though the data itself is now a probabilistic approximation! This is why CRDTs and probabilistic data structures pair so beautifully.

Lab

State-based CRDTs merge with a join ⊔ that is commutative, associative, and idempotent. A G-Counter takes per-replica max; summing replica vectors after a partition over-counts. Probabilistic tombstones compress deletes into a Bloom filter — occasional false positives drop stale adds.

Replica A[A:0, B:0, C:0]Σ = 0

Replica B[A:0, B:0, C:0]Σ = 0

Merged[A:0, B:0, C:0]Σ = 0

Replica A

Replica B

Lattice edges flow A, B → ⊔. After Partition heal, both replicas show 3× on Node_A — max gives 3, naive sum gives 6.

Replica totals are A=0, B=0. After ⊔ (componentwise max), is the merged total 0 equal to the naive sum 0?

G-Counter ⊔ total 0.