CRDT OR-Set (Replica Merge)

How two offline devices magically merge their shopping carts without conflicts.

The idea

In distributed systems without a central leader (like local-first apps or multi-master databases), two users might edit a set while completely offline. User A adds "Apples". User B removes "Apples". When they reconnect, how do we merge their states? If we just use timestamps, clock drift can delete data. A CRDT OR-Set (Conflict-Free Replicated Data Type: Observed-Remove Set) solves this perfectly by giving every newly added item a unique, invisible tag.

Step 1: Alice and Bob start with a synchronized cart containing one item.

How it works (Add Sets and Remove Sets)

Under the hood, an OR-Set is actually TWO sets: an AddSet and a RemoveSet. When you add an item, you attach a random UUID (tag) and put it in the AddSet. When you remove an item, you look at all the tags you currently observe for that item, and put them in the RemoveSet. The final visible set is simply: AddSet - RemoveSet.

# The internal math of an OR-Set Merge
# State A (Alice offline): Adds 'Apple' with a new tag
A_Add = {("Milk", t1), ("Apple", t2)}
A_Rem = {}

# State B (Bob offline): Removes 'Milk' (he observed tag t1)
B_Add = {("Milk", t1)}
B_Rem = {("Milk", t1)}

# MERGE! We just union the AddSets, and union the RemoveSets
Merged_Add = A_Add U B_Add = {("Milk", t1), ("Apple", t2)}
Merged_Rem = A_Rem U B_Rem = {("Milk", t1)}

# Visible Items = Merged_Add minus Merged_Rem
Visible = {"Apple"} # Milk is removed, Apple is kept! Conflict free.

Cost

CRDTs use more memory. Instead of storing just the word "Milk", you must store ("Milk", "uuid-1234-..."). Furthermore, the RemoveSet grows forever (tombstones). In long-running systems, you must implement complex "Garbage Collection" to clean up the RemoveSet once you prove all nodes have seen the deletion.

Watch out for