CRDTs: convergence requires algebra and delivery assumptions

A state-based CRDT uses a join-semilattice, inflationary local updates, and least-upper-bound merge. Associative, commutative, idempotent join tolerates state reordering and duplication. A delta-state CRDT sends joinable deltas but keeps the same algebra and anti-entropy obligations.

An operation-based CRDT has a different contract: concurrent effectors commute and non-commuting dependencies receive causal delivery. Unique dots and duplicate handling remain explicit. Replica convergence does not prove application invariants such as unique names or nonnegative stock.

Prerequisites and model

• The payload, causal metadata, merge/effect function, and delivery assumptions are one protocol.
• Replica and element identities remain unique across restart and garbage collection.
• Application invariants are analyzed separately from convergence.

Correctness claims and invariants

• CRDT-C1. State-based convergence requires a join-semilattice, inflationary updates, and repeated LUB merge.
• CRDT-C2. Associative, commutative, idempotent join tolerates reordered and duplicate state delivery.
• CRDT-C3. Operation-based convergence requires concurrent effectors to commute and stated causal/reliability delivery.
• CRDT-C4. Observed-remove sets need unique add tags and an explicit add-wins or remove-wins rule.
• CRDT-C5. Tombstones or dots are compacted only after causal stability excludes relevant old operations.
• CRDT-C6. Delta CRDTs retain the lattice contract while reducing transfer granularity.
• CRDT-C7. Some invariants are not coordination-free even when all replicas converge.

What the scenarios prove

• State grow-only counter (state-gcounter): Replica components grow and join by componentwise maximum.

▶Walkthrough: state-gcounter (not found)

• Duplicate state (duplicate-state): Idempotent join makes repeated state harmless.

▶Walkthrough: duplicate-state (not found)

• PN-counter invariant boundary (pn-counter): Counter convergence does not preserve nonnegative inventory.

▶Walkthrough: pn-counter (not found)

• Observed-remove add-wins set (or-set-add-wins): A remove deletes observed tags; an unseen concurrent add survives.

▶Walkthrough: or-set-add-wins (not found)

• Operation causal delivery (operation-causal-delivery): A dependent non-commuting operation waits for its predecessor.

▶Walkthrough: operation-causal-delivery (not found)

• Duplicate operation dot (duplicate-operation): At-least-once delivery cannot apply one dot twice.

▶Walkthrough: duplicate-operation (not found)

• Causally stable tombstone GC (tombstone-gc): Compaction waits until old operations cannot reappear.

▶Walkthrough: tombstone-gc (not found)

• Global invariant coordination (invariant-coordination): Two locally valid reservations can jointly oversell.

▶Walkthrough: invariant-coordination (not found)

Failure, concurrency, and retry traps

• An ad-hoc JSON merge is not a CRDT without the required algebra.
• A PN-counter may converge to negative inventory.
• Operation redelivery needs a unique dot and idempotent effect or dedupe.
• Deleting tombstones by age can resurrect removed elements when an old replica reconnects.

Boundaries and non-guarantees

• Convergence is not consensus, linearizability, or application correctness.
• Add-wins and remove-wins are product semantics, not universal answers.
• State growth, causal metadata, and anti-entropy bandwidth are design costs.

Related material

[CONCEPT]consistency-models [CONCEPT]vector-clocks [CONCEPT]happens-before [CONCEPT]gossip-protocol [CONCEPT]offline-first [CASE]google-docs-collab [CASE]distributed-key-value-store

Primary sources

1. Shapiro et al., A Comprehensive Study of CRDTs
2. Shapiro et al., Conflict-free Replicated Data Types
3. Almeida, Shoker, Baquero: Delta State Replicated Data Types
4. Bailis et al., Coordination Avoidance in Database Systems