Gset

GSet, short for Grow-only Set, is a simple conflict-free replicated data type (CRDT) that models a set of elements in distributed systems where only additions are allowed. The state of a GSet is a set of elements, and the sole mutating operation is add(x), which updates the state to S ∪ {x}. A membership query simply checks whether an element is contained in the current state.

In a distributed environment, two replicas with states S1 and S2 can be reconciled by merging them, where the merged state is S1 ∪ S2. This merge is associative, commutative, and idempotent, ensuring convergence without coordination. Once an element is added on any replica, it will eventually appear on all replicas after propagation, provided the updates are delivered.

Because deletions are not supported, a GSet is inherently monotonic: elements, once added, cannot be removed. This simplicity makes it robust and easy to implement, but it also limits applicability to use cases where deletions are unnecessary or can be modeled indirectly.

Implementation and usage notes: a GSet can be implemented as a normal set data structure on each replica, with state synchronization accomplished by union operations during merges. In practice, updates propagate via replication mechanisms such as gossip, log-based replication, or CRDT-aware messaging. GSets are often used as building blocks for more expressive CRDTs, such as the 2P-Set, which combines two grow-only sets to support add and remove semantics with the restriction that removed elements cannot be re-added, as well as for simple tagging or event-tracking scenarios where deletions are not required.