ORSet

A set where elements can be added and removed. When two devices edit at the same time — one adds an item, another removes it — add wins. The item stays in.

Converges to: a set containing exactly the elements whose add operations have not been causally dominated by a subsequent remove from a replica that observed that add.

Merge rule

Every add(replica, element) tags the element with a unique dot (replica, counter). A remove(element) witnesses all dots currently associated with the element in the local state and marks them as removed. On merge:

A dot present in only one replica's store (the other never saw it) is kept.
A dot present in the store of A but in the causal context of B (B saw it and removed it) is dropped.

This is why add wins over a concurrent remove: a concurrent remove only witnessed dots it already had. A new dot minted by the concurrent add was never seen by the remover, so it survives.

Code examples

Add then contains:

    @Test
    fun addThenContains() {
        val s = ORSet.empty<String>().add(a, "card")
        assertTrue(s.contains("card"))
        assertEquals(setOf("card"), s.elements)
    }

Add wins over concurrent remove:

    @Test
    fun addWinsOverConcurrentRemove() {
        // shared start: A added "card"
        val start = ORSet.empty<String>().add(a, "card")
        val alice = start.remove("card")     // Alice removes what she saw
        val bob = start.add(b, "card")       // Bob concurrently re-adds
        val merged = alice.piece(bob)
        assertTrue(merged.contains("card"))  // add wins
    }

Remove wins when it observed the add:

    @Test
    fun removeWinsWhenNothingConcurrentlyAdded() {
        val start = ORSet.empty<String>().add(a, "card")
        val alice = start.remove("card")
        // Bob did nothing new; merging the removal with the stale-present state drops it
        val merged = alice.piece(start)
        assertFalse(merged.contains("card"))
    }

When to use

ORSet is the right choice for most concurrent set workloads where elements can be re-added after removal. Add-wins semantics are intuitive: a concurrent re-add "undoes" a concurrent remove. For permanent removal (tombstone-wins), see TwoPhaseSet.

Last modified: 22 June 2026