LWWSet

LWW-Set, short for Last-Writer-Wins Set, is a conflict-free replicated data type (CRDT) that implements a set with add and remove operations using last-writer-wins semantics. It enables replicas in a distributed system to converge to the same state without requiring centralized coordination, even in the presence of concurrent updates.

The standard LWW-Set is implemented with two timestamped stores per element: an adds map and a removes map. For each element, the last timestamp at which it was added and the last timestamp at which it was removed are recorded. A membership query yields true if the last add timestamp is greater than the last remove timestamp (add_ts > remove_ts); otherwise, the element is considered absent. If there is no add timestamp for an element, it is not present, and if there is no remove timestamp, it is treated as not removed.

Operations and merging are defined as follows. add(element, ts) updates the adds map with add_ts = max(add_ts, ts). remove(element, ts) updates the removes map with remove_ts = max(remove_ts, ts). When two replicas synchronize, their respective adds and removes maps are merged by taking, for each element, the maximum add timestamp and the maximum remove timestamp. The eventual state after merging respects the rule add_ts > remove_ts for membership, thus supporting eventual consistency.

Variations exist, most notably add-wins (the standard form) and remove-wins, which differ in how ties are resolved when timestamps are equal. In add-wins, an element remains in the set if its add timestamp is greater than its remove timestamp. In remove-wins, removal takes precedence, typically by adjusting the tie-breaking rule.

LWW-Set is simple to implement and merge, but it relies on timestamp synchronization and can grow unbounded with the number of distinct elements. It is suited for scenarios requiring simple replication and offline updates, such as distributed caches or session stores.