Conflict-free replicated data type
A conflict-free replicated data type permits local updates and guarantees convergence under specified merge and delivery rules.
Convergence: Replicas incorporating the same updates have equivalent states. State-based designs use inflationary updates and a least-upper-bound merge. Operation-based designs instead require compatible operations and delivery guarantees; the original model assumes reliable, causal, exactly-once delivery. [1]
Counter: A grow-only counter retains one component per replica, increments only the local component, merges by componentwise maximum and queries the sum. Fixed distinct identities and non-overflowing counters matter. Replaying a state does not add its increments twice; executing a client increment twice is two updates. [2]
Storage: Convergence does not itself make an acknowledgement durable; persistent storage is a separate implementation choice. Delta delivery requirements also depend on the data type. An UpdateTimeout is not rollback evidence. [3]
Bounds: A convergent counter does not automatically preserve an inventory limit. A bounded counter distributes rights, so local availability depends on the rights held at that replica. [4]
Relations
Citations
- Shapiro et al. Conflict-free Replicated Data Types. SSS 2011, sections 2.2-2.4.
- Shapiro et al. A comprehensive study of Convergent and Commutative Replicated Data Types. RR7506 (2011), section 3.1.2.
- Akka 2.11.0 documentation: Distributed Data, Durable Storage and Delta CRDTs (version displayed at access).
- Balegas et al. Extending Eventually Consistent Cloud Databases for Enforcing Numeric Invariants (2015), sections II-IV.
Sources & caveats
- Primary-source synthesis of the 2011 convergence models and counter construction; no distributed implementation or benchmark was run.
- The linked counter illustration adapts RR7506 section 3.1.2. Finite arithmetic tests check the example, not a replication protocol.