CRDT Primitives — Muse Developer Docs

The three lattice laws

A CRDT is a data structure paired with a merge (join) operation that satisfies three algebraic properties. When these hold, any set of replicas that exchange states in any order will eventually reach the same value — convergence without coordination.

⊕

Commutativity

a ⊕ b = b ⊕ a

Order of merge does not matter. Replica A merging B then C reaches the same state as replica A merging C then B.

∘

Associativity

(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)

Grouping of merges does not matter. Batch and streaming synchronization strategies produce identical results.

=

Idempotency

a ⊕ a = a

Merging a state with itself is a no-op. Duplicate delivery of the same update — common in distributed systems — has no effect.

All six primitives in muse/core/crdts/ are proven to satisfy these laws. Their merge() methods are the join operation. State grows monotonically — you can add information but never remove it from a CRDT state directly (deletion is encoded as a tombstone or carried in an add-wins set).

All primitives live in muse/core/crdts/ and are imported from muse.core.crdts. They are pure Python with no external dependencies. Each exports a State TypedDict and a merge(a, b) function.

Six primitives

Type	Module	Use case
VectorClock	vector_clock.py	Causal ordering; happens-before detection across agents
LWWRegister	lww_register.py	Last-writer-wins scalar; safe for isolated, rarely-contested fields
ORSet	or_set.py	Add-wins set; tracks tags, labels, memberships
RGA	rga.py	Replicated Growable Array; ordered sequences with position stability
AWMap	aw_map.py	Add-wins map; nested key-value state with per-key CRDT values
GCounter	gcounter.py	Grow-only counter; download counts, event tallies, play counts

VectorClock

A map from node ID to logical timestamp. Tracks causal order across distributed agents without a central clock. The merge is component-wise max — two independent clocks converge to the least upper bound of both.

VectorClock causal order

State: dict[str, int] — node_id → logical timestamp

increment(clock: State, node_id: str) -> State merge(a: State, b: State) -> State # component-wise max happens_before(a: State, b: State) -> bool concurrent(a: State, b: State) -> bool

Used in: Harmony audit log; agent coordination DAG; commit causality in multi-agent branches.

LWWRegister

Last-writer-wins register. Stores a value paired with a timestamp; merge keeps the value with the highest timestamp. Simple but lossy — the losing write is discarded. Safe for rarely-contested fields where the latest value is always correct (e.g. a display name, a status flag).

LWWRegister last-writer-wins

State: {"value": Any, "timestamp": float}

set(reg: State, value: Any, ts: float) -> State get(reg: State) -> Any merge(a: State, b: State) -> State # max(a.ts, b.ts)

Used in: MIDI domain — tempo, time signature, key signature (single authoritative value per song position).

ORSet

Observed-Remove Set. Each add operation tags the element with a unique token. Removal records the token, not just the element. When a remove and an add are concurrent, add wins — the element stays if any un-removed add token exists. This is the correct semantic for tags, labels, and membership where concurrent additions should be preserved.

ORSet add-wins

State: {"elements": {val: {token, ...}}, "tombstones": {token, ...}}

add(s: State, element: Any) -> State remove(s: State, element: Any) -> State contains(s: State, element: Any) -> bool value(s: State) -> frozenset merge(a: State, b: State) -> State

Used in: Proposal labels, issue labels, repo topics. Concurrent tag additions from multiple agents all survive.

RGA

Replicated Growable Array. An ordered sequence CRDT where each element carries a unique identifier (site + sequence number). Insertions are positioned relative to a predecessor element ID — positions remain stable as other elements are inserted concurrently. Deletions leave tombstones; value() filters them out for the live sequence.

RGA ordered sequence

State: list of RGANode(id, value, tombstone)

insert(s: State, after_id: str|None, val: Any, site: str) -> State delete(s: State, element_id: str) -> State value(s: State) -> list[Any] # tombstones filtered merge(a: State, b: State) -> State

Used in: Ordered MIDI note sequences; comment threads where insertion order must be preserved across concurrent replies.

AWMap

Add-Wins Map. A map where each value is itself a CRDT. Concurrent writes to the same key are merged using the value CRDT's own merge function. Concurrent removal and update of the same key resolves as add-wins — the key survives. The map grows monotonically; keys can only be removed with an explicit tombstone.

AWMap add-wins map

State: {"entries": {key: CRDTState}, "tombstones": {key}}

set(m: State, key: str, val_state: CRDTState) -> State remove(m: State, key: str) -> State get(m: State, key: str) -> CRDTState | None keys(m: State) -> set[str] merge(a: State, b: State) -> State

Used in: Address-keyed domain state (e.g., per-note MIDI attributes where the address is pitch + onset; per-symbol code metadata where the address is the symbol path).

GCounter

Grow-only counter. Each node increments its own slot; the global value is the sum of all slots. Merge is component-wise max. Cannot decrement — if you need a PN-counter (positive/negative), compose two GCounters.

GCounter grow-only

State: dict[str, int] — node_id → local count

increment(c: State, node_id: str, by: int = 1) -> State value(c: State) -> int # sum of all slots merge(a: State, b: State) -> State # component-wise max

Used in: Mist download counts, repo star counts, play counts — any metric that only grows and must be consistent across distributed replicas.

CRDTPlugin — integrating with your domain

If your domain's merge logic can be expressed entirely as CRDT state transitions, implement CRDTPlugin instead of (or alongside) MuseDomainPlugin. The engine calls to_crdt_state() before merge and from_crdt_state() after — your domain object never needs to know about the CRDT internals.

Python CRDTPlugin interface

class CRDTPlugin(MuseDomainPlugin):
    def crdt_schema(self) -> list[CRDTDimensionSpec]:
        """Declare the CRDT type used for each dimension."""

    def join(self, a: CRDTSnapshotManifest, b: CRDTSnapshotManifest) -> CRDTSnapshotManifest:
        """Lattice join — commutative, associative, idempotent."""

    def to_crdt_state(self, snapshot: StateSnapshot) -> CRDTSnapshotManifest:
        """Lift a plain snapshot into CRDT state representation."""

    def from_crdt_state(self, crdt: CRDTSnapshotManifest) -> StateSnapshot:
        """Materialise a CRDT state back to a plain snapshot."""

The CRDT plugin path bypasses Harmony's three-tier conflict resolution — convergence is mathematical, not heuristic. Use it when your domain's conflict semantics are provably expressible as a lattice join. When in doubt, start with MuseDomainPlugin and add CRDTPlugin later.

When not to use CRDTs

CRDTs trade expressiveness for convergence guarantees. They are not always the right tool.

Scenario	Use instead
Strong consistency required	Harmony policy with `merge_mode: three-way` and human escalation
Complex semantic invariants (e.g. "no two notes at the same pitch and onset")	`MuseDomainPlugin.merge()` with explicit invariant checks post-merge
Deletion must win over concurrent addition	Custom tombstone logic in `MuseDomainPlugin`
History must be auditable and reversible	TypedDelta op log via `AddressedMergePlugin` — ops are preserving, not lossy
State is too large for in-memory CRDT (millions of elements)	Sharded domain with per-shard CRDTs + coordination-layer fan-out