Operation-based CRDTs: commutativity needs a delivery contract

A source can inspect its current state while preparing an update, then produce an effect containing enough information for downstream replicas. For an observed-remove set, for example, a remove must identify the add tags it actually observed, rather than telling every receiver to delete whichever additions happen to exist on arrival. Preparation and effect application are separate conceptual phases, even if an implementation combines them in one API. A downstream replica should not independently reinterpret the original user command against unrelated local context.

In the standard causal operation-based model, reliable delivery eventually makes each effect available at correct replicas, causal order preserves prerequisite effects, and concurrent effects commute. Some particular types need weaker ordering; other designs incorporate additional metadata to tolerate stronger reordering. State the actual contract rather than claiming all operation-based CRDTs work over arbitrary lossy, duplicated messages. A convergence proof that assumes once-only effect delivery does not survive blindly replaying a non-idempotent increment every time a network retry arrives.

A signed counter whose operations add fixed deltas has commuting effects, but adding the same delta twice still counts it twice. Give each logical operation a unique identity and ensure the dissemination layer applies its effect once, or design an idempotent representation that absorbs repeats. Durable deduplication state, actor epochs, and replay boundaries matter across crashes. A locally generated operation that was already applied must not be applied again merely because the source receives its own replicated message.

The phrase exactly once needs a boundary. A transport may redeliver, while a consumer transaction records an operation identity together with its state change. An external email or payment is another side effect that is not automatically protected by an in-memory CRDT’s delivery logic. Likewise, forgetting deduplication records requires evidence that old messages cannot return or that an epoch rejects them. Convergence of the in-memory type does not provide unlimited replay protection outside its documented retained history.

If accepted operations accumulate faster than the replication channel can deliver them, the backlog grows even when every algebraic condition is correct. Measure pending effects, oldest-undelivered age, retry traffic, and the size of deduplication metadata. Durable logs and anti-entropy can repair gaps, but their retention and recovery rules must align. A permanently lost accepted operation contradicts eventual delivery; good local latency alone cannot establish eventual convergence. Overload policies should be explicit about whether an operation was actually accepted.

The queue lab gives a limited view of this delivery-capacity pressure. Reset, set arrival rate λ=4 and service rate μ=3, predict backlog 4+t, then Step or Play. Reset again and set λ=2, μ=3 to predict drainage to zero at t=4. Editing controls alone preserves elapsed time, so Reset is needed for this fresh comparison. The fluid queue contains no operation identities, causality, retries, or deduplication; its separately labeled M/M/1 estimate has additional stochastic assumptions.