TwoPhaseSet

A set where removal is final. Elements can be added and removed, but once removed they can never come back. When an add and a remove happen at the same time, remove wins.

Converges to: the set of elements that have been added and not yet tombstoned, where tombstones are permanent.

Merge rule

A TwoPhaseSet maintains two GSets: an add-set A and a tombstone-set R. An element is present if element ∈ A ∧ element ∉ R. Merge is union of both sets independently. Because tombstones only grow, a tombstoned element remains absent in all future states — even if another replica concurrently adds it.

Code examples

Add and remove:

    @Test
    fun addThenContains() {
        val s = TwoPhaseSet.empty<String>().let { it.piece(it.add("x")) }
        assertTrue(s.contains("x"))
    }

    @Test
    fun removeMakesAbsent() {
        val s = TwoPhaseSet.empty<String>().let { it.piece(it.add("x")) }
        val gone = s.piece(s.remove("x"))
        assertFalse(gone.contains("x"))
    }

Remove wins over concurrent re-add:

    @Test
    fun removeWinsOverConcurrentReAdd() {
        // start: "x" added. Alice removes; Bob (unaware) re-adds.
        val start = TwoPhaseSet.empty<String>().let { it.piece(it.add("x")) }
        val alice = start.piece(start.remove("x"))
        val bob = start.piece(start.add("x"))
        // The merge: tombstone wins forever. "x" stays gone.
        assertFalse(alice.piece(bob).contains("x"))
    }

Tombstone is permanent — resurrection is impossible:

    @Test
    fun cannotResurrectARemovedElement() {
        // Even on a later isolated add — tombstone permanence is the contract.
        val s = TwoPhaseSet.empty<String>()
            .let { it.piece(it.add("x")) }
            .let { it.piece(it.remove("x")) }
        val retried = s.piece(s.add("x"))
        assertFalse(retried.contains("x"))
    }

When to use

TwoPhaseSet is appropriate when removal semantics must be final — expired tokens, retired identifiers, blacklisted entries. For a set where removed elements can be re-added, use ORSet.

Last modified: 22 June 2026