hecate_or_set (macula v10.19.0)

View Source

Observed-Remove Set CRDT (Part 3 §7.4).

Realm-shared mutable state (member lists, chat threads, directory metadata) converges across nodes without coordination. Each add/2 tags the element with a unique 16-byte random tag; remove/2 tombstones every currently observed tag. Concurrent add+remove of the same element keeps the element (the new tag wasn't observed by the remover) — the property that makes OR-Set the right CRDT for "did Alice add a member just before I removed?" semantics.

State

  • data :: #{Element => sets:set(Tag)} — currently-active tags per element. An element is "in the set" iff its tag set is non-empty.
  • tombstones :: sets:set(Tag) — tags removed by an observed remove/2. New deltas carrying these tags are suppressed so a delayed re-broadcast of a removed add cannot resurrect the element.

Convergence

Two interfaces:

  • merge/2 — full-state union for catch-up sync. Combines tag sets element-wise, subtracts the unioned tombstone set, drops elements that lose all live tags.
  • apply_delta/2 — incremental delta application for per-op gossip over Plumtree. Applies one {add, Element, Tag} or {remove, [Tag]} delta.

Both produce the same final state given the same total set of operations — the OR-Set's strong eventual consistency guarantee.

Reference: plans/PLAN_MACULA_V2_PART3_DISCOVERY.md §7.4; plans/PLAN_PHASE_5_BREAKDOWN.md Session 5.4.

Summary

Types

delta/0
element/0
or_set/0
tag/0

Functions

add(Set, Element)

Add Element with a fresh tag. Returns the new set plus the delta to broadcast.

apply_delta(Set, _)

Apply a single delta (the per-op product of add/2 or remove/2). Idempotent — re-applying the same delta is a no-op. Tombstoned tags are silently suppressed in add deltas so a delayed re-broadcast cannot resurrect a removed element.

contains(_, Element)
is_empty(Set)
members(_)
merge(_, _)

Full-state union — element-wise tag union, then subtract the merged tombstones, then drop elements with no live tags.

new()
remove(Set, Element)

Remove Element by tombstoning every currently-observed tag. If the element is absent the operation is a no-op (delta carries an empty tag list).

size(Set)
tags_for(_, Element)
tombstone_count(_)
tombstones(_)

Types

delta/0

-type delta() :: {add, element(), tag()} | {remove, [tag()]}.

element/0

-type element() :: term().

or_set/0

-type or_set() :: #{data := #{element() => sets:set(tag())}, tombstones := sets:set(tag())}.

tag/0

-type tag() :: <<_:128>>.

Functions

add(Set, Element)

-spec add(or_set(), element()) -> {or_set(), delta()}.

Add Element with a fresh tag. Returns the new set plus the delta to broadcast.

apply_delta(Set, _)

-spec apply_delta(or_set(), delta()) -> or_set().

Apply a single delta (the per-op product of add/2 or remove/2). Idempotent — re-applying the same delta is a no-op. Tombstoned tags are silently suppressed in add deltas so a delayed re-broadcast cannot resurrect a removed element.

contains(_, Element)

-spec contains(or_set(), element()) -> boolean().

is_empty(Set)

-spec is_empty(or_set()) -> boolean().

members(_)

-spec members(or_set()) -> [element()].

merge(_, _)

-spec merge(or_set(), or_set()) -> or_set().

Full-state union — element-wise tag union, then subtract the merged tombstones, then drop elements with no live tags.

new()

-spec new() -> or_set().

remove(Set, Element)

-spec remove(or_set(), element()) -> {or_set(), delta()}.

Remove Element by tombstoning every currently-observed tag. If the element is absent the operation is a no-op (delta carries an empty tag list).

size(Set)

-spec size(or_set()) -> non_neg_integer().

tags_for(_, Element)

-spec tags_for(or_set(), element()) -> [tag()].

tombstone_count(_)

-spec tombstone_count(or_set()) -> non_neg_integer().

tombstones(_)

-spec tombstones(or_set()) -> [tag()].