The "Zombie Element" Problem
LWW sets have a subtle failure mode called the add-wins / remove-wins ambiguity. Consider this scenario:
- Alice adds "Apple" to a shared shopping list.
- Alice removes "Apple" (she changed her mind).
- Bob, who was offline, also adds "Apple" independently.
- Bob comes online and syncs.
Should "Apple" be in the list? Intuitively, yes — Bob added it after Alice removed it (from his perspective). But with LWW, the answer depends entirely on whose clock is more accurate. This is the "zombie element" problem: items that should be alive get killed, or items that should be dead come back.
Unique Tags: Tracking Specific Instances
The Observed-Remove Set (OR-Set) solves this by tracking specific instances of additions, not just the element itself.
When you add an element, the CRDT generates a globally unique tag (a UUID) for that specific add operation:
Add("Apple") → stores ("Apple", uuid-a1f3)
When you remove an element, you don't say "remove Apple." You say "remove the specific Apple instances I have observed":
Remove("Apple") → stores removal of {uuid-a1f3}
The key insight: Bob's independent add of "Apple" gets a different UUID:
Bob: Add("Apple") → stores ("Apple", uuid-b7c2)
When Alice's removal of uuid-a1f3 and Bob's addition of uuid-b7c2 are merged:
- uuid-a1f3 is removed ✅
- uuid-b7c2 is present and NOT in any removal set ✅
- Therefore "Apple" exists in the merged state.
This accurately reflects intent: Alice removed her Apple. Bob added his Apple. They're different events.
OR-Set State at Any Point
Add Set: {("Apple", uuid-a1f3), ("Apple", uuid-b7c2)}
Remove Set: {uuid-a1f3}
Effective elements = Add Set elements whose UUID is NOT in Remove Set
= {("Apple", uuid-b7c2)}
= {"Apple"} ✅
The Trade-off
OR-Sets are more correct than LWW-Sets but require storing UUIDs for every add operation. In a long-lived dataset with many additions and removals, the sets can grow large. Production implementations use tombstone garbage collection — periodically compacting the sets when all replicas have acknowledged a removal — but this requires coordination and is one of the harder engineering challenges in CRDT systems.
A common interview question: "What's the difference between an LWW-Set and an OR-Set, and when would you use each?" The answer: LWW-Set uses timestamps and can silently lose data under clock skew; OR-Set uses unique tags per addition and preserves intent at the cost of storage. Use LWW for metrics/caches where occasional data loss is acceptable; use OR-Set for user-facing collaborative features where every action must be preserved.
Key Point: OR-Sets are the standard for collaborative list and set implementations precisely because they preserve user intent. The UUID-per-addition design means removals are surgical — they target a specific observed state, not all future states.