CmRDT

CmRDT stands for Commutative Replicated Data Type, a category of conflict-free replicated data types used in distributed systems. In a CmRDT, updates are expressed as operations that commute, so applying concurrent updates in any order yields the same final state. This distinguishes CmRDTs from state-based CRDTs that rely on merging full states.

How CmRDTs work: when a client issues an update, it is transformed into an operation and propagated to all replicas via an anti-entropy or broadcast mechanism. Each replica applies the operation locally, and duplicates are handled so that repeated receptions do not change the outcome. The key requirement is that all concurrent operations commute and are applied in a way that does not depend on order. Reliability or causal delivery guarantees, unique operation identifiers, and deduplication are common design considerations to ensure convergence.

Comparison to CvRDTs: CvRDTs propagate and merge state using a join operation on a lattice, whereas CmRDTs propagate operations that transform state. CmRDTs often reduce communication overhead when updates are frequent, since only the incremental operations are sent rather than full state. However, CmRDT design requires that updates be expressible as commuting operations, which may not be possible for all data types or semantics.

Variants and practices: practice includes operation-based CRDTs and delta-state CRDTs, where a delta describes the effect of an operation so that only the incremental change is shared. These approaches aim to balance convergence guarantees with communication efficiency.

Limitations: not all data types admit commuting updates, and designing correct concurrent semantics can be challenging. Proper handling of delivery guarantees and idempotence is essential to avoid divergence.