2PSet
2P-Set, short for two-phase set, is a type of conflict-free replicated data type (CRDT) used in distributed systems to achieve eventual consistency for sets. It is implemented as a pair of grow-only sets, typically denoted A and R. The current value of the 2P-Set is the set difference A \ R (elements that have been added but not removed).
- Add(x): A := A ∪ {x}. This operation is monotonic; elements can only be added to A.
- Remove(x): R := R ∪ {x}. This operation is also monotonic; elements can only be added to R.
- Membership(x) (query): x is considered a member of the 2P-Set if x ∈ A and x ∉ R.
- Each replica maintains its own (A, R). When replicas synchronize, they merge by taking unions: A :=
- Because both A and R are grow-only and merges use set union, the replicas converge to a
- The semantics ensure commutativity, associativity, and idempotence of merges, which are core CRDT properties.
- A key limitation is that once an element is removed (i.e., added to R), it cannot be
- This makes 2P-Set unsuitable for scenarios requiring re-introduction of elements after removal or frequent churn.
- For applications needing re-adding semantics, other CRDTs such as the Observed-Removed Set (OR-Set) or more complex
- Scenarios where elements are added and removed but re-addition is either rare or undesirable, and where