CoreConcept & Pseudocode Entry

CRDT OR-Set (Observed-Remove Set)

Conflict-free replicated set that resolves concurrent offline add and remove operations deterministically (add-wins) by tagging each added element with a unique token.

Explore relationships Open 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Distributed Systems
Difficulty: Intermediate
Family: Conflict-Free Replicated Data Types (CRDTs)
Tier: Core
Status: Reviewed
Review: AI Reviewed
Sources: 1
Formulas: 1
Relationships: 3
Code example: Not ready
Visualization: Ready
Aliases: OR-Set CRDT, Add-Wins Set CRDT, Conflict-Free Replicated Set, CRDT

Overview

An OR-Set (Observed-Remove Set CRDT) allows distributed or offline replicas to add and remove set elements concurrently without a central server or coordination. Each add(e) generates a globally unique tag u = (replicaId, counter) and inserts (e, u) into the active tag set. A remove(e) only tombstones the tags of e currently observed at that replica. When two replicas merge (by taking the union of added tags and the union of tombstoned tags), a concurrent add(e) and remove(e) preserves the newly added tag ('add-wins'), and elements can be re-added freely after removal.

Core Concepts

unique add-tag tokensobserved-remove tombstonesadd-wins concurrency semanticsjoin-semilattice union

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1) local add/lookup

Average

O(|tags|) state merge

Worst

O(|tags|)

Space

O(|unique add tags|) or O(|elements| + |replicas|) in optimized causal-context ORSWOT

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for CRDT OR-Set (Observed-Remove Set) across input scales.

Input Scale N:

JIT-compiled JS/TS (~350M primitive ops/sec)

Est. Average TimeO(|tags|) state merge

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops

Est. Worst-Case TimeO(|tags|)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops

1.53 MB

Standard Heap FitN=100,000

When to Use

Use an OR-Set CRDT when replicas or offline devices must concurrently add and remove items from a shared collection and merge without a central server or lock.
Use it instead of a 2P-Set (Two-Phase Set) whenever removed elements must be able to be added again later.

When Not to Use

Avoid naive tombstone-accumulating OR-Set without causal version-vector compaction (ORSWOT) if millions of transient elements are added and deleted.

What It Does

Merges concurrent set additions and removals across offline or partitioned replicas without conflicts or central coordination
Allows elements to be removed and re-added arbitrarily while guaranteeing strong eventual consistency

Use Cases

Shopping carts, collaborative playlists, and shared document tag sets in offline-first apps
Multi-datacenter active-active replicated sets in Riak, Redis Enterprise, and Dynamo-style stores
Peer-to-peer state synchronization without a central server or consensus leader

Inputs

Local add(element) / remove(element) operations and remote replica state (AddSet, RemoveTombstones)

Outputs

Converged set of present elements {e | exists tag u: (e, u) in AddSet \ RemoveTombstones}

Key Formulas (1)

OR-Set Membership & Merge

present(e) ≤> (A(e) \ R) ≠ empty; merge((A₁, R₁), (A₂, R₂)) = ((A₁ union A₂) \ (R₁ union R₂), R₁ union R₂)

present(e) <=> (A(e) \ R) != empty; merge((A_1, R_1), (A_2, R_2)) = ((A_1 union A_2) \ (R_1 union R_2), R_1 union R_2)

Union of observed add-tags minus union of observed remove-tombstones forms a bounded join-semilattice.

Pseudocode

1.Maintain map entries: element -> Set of active unique tags, and tombstones: Set of removed tags
2.On add(e) at replica i: generate unique tag u = (i, ++seq); add u to entries[e]
3.On remove(e) at replica i: add all tags currently in entries[e] to tombstones; clear entries[e]
4.On lookup(e): return true iff (entries[e] \ tombstones) is non-empty
5.On merge(remote): tombstones = tombstones union remote.tombstones; for each e: entries[e] = (entries[e] union remote.entries[e]) \ tombstones

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

Maintain map entries: element -> Set of active unique tags, and tombstones: Set of removed tags
On add(e) at replica i: generate unique tag u = (i, ++seq); add u to entries[e]
On remove(e) at replica i: add all tags currently in entries[e] to tombstones; clear entries[e]
On lookup(e): return true iff (entries[e] \ tombstones) is non-empty
On merge(remote): tombstones = tombstones union remote.tombstones; for each e: entries[e] = (entries[e] union remote.entries[e]) \ tombstones

Canonical Example

Input: Both replicas hold ('apple', tag1); Replica A runs remove('apple') while offline Replica B runs add('apple') -> tag2; merge A and B
Output: 'apple' remains in the merged set with active tag2 (add-wins)
Explanation: Replica A only observed and tombstoned tag1; Replica B's concurrent tag2 was not in A's observed set, so tag2 survives the merge.

Implementation Notes

In production (ORSWOT — Observed-Remove Set Without Tombstones), summarize seen tags with a compact per-replica causal version vector.

Common Pitfalls

Using a simple boolean flag per element instead of unique per-add tags, which either prevents re-adding removed elements (2P-Set) or loses causal ordering.
Removing unseen concurrent add tags instead of only removing the tags currently observed on the local replica.