Source-linked AI summary
Delta State Replicated Data Types
Paulo Sérgio Almeida, Ali Shoker, Carlos Baquero
TL;DR
State-based CRDTs can send large full states, while operation-based CRDTs assume reliable exactly-once causal broadcast. The paper introduces δ-CRDTs, which disseminate incremental states through joins, and reports that they preserve CRDT properties while supporting eventual and causal consistency.
Problem
Method
The paper defines δ-mutators that return incremental delta-states for replicas to join, and develops anti-entropy algorithms for eventual and causal consistency.
Source: §1 · pp. 2–3Results
δ-CRDTs preserve the key join properties of standard state-based CRDTs while allowing smaller delta-states to be shipped instead of full states.
Source: §1 · p. 2, §9 · p. 25Takeaways & Limitations
δ-CRDTs can replace classical state-based CRDTs without losing their power and can also ship individual deltas with weaker dissemination guarantees than operation-based CRDTs.
Source: §9 · p. 25Operation-based CRDTs assume reliable exactly-once causal broadcast, which the paper describes as hard to maintain because large logs must be retained to prevent duplication.
Source: §1 · p. 2
Abstract
from arXiv · showhide
CRDTs are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs ensure convergence through disseminating the entire state, that may be large, and merging it to other replicas; whereas operation-based CRDTs disseminate operations (i.e., small states) assuming an exactly-once reliable dissemination layer. We introduce Delta State Conflict-Free Replicated Data Types ($\delta$-CRDTs) that can achieve the best of both worlds: small messages with an incremental nature, as in operation-based CRDTs, disseminated over unreliable communication channels, as in traditional state-based CRDTs. This is achieved by defining delta mutators to return a delta-state, typically with a much smaller size than the full state, that to be joined with both local and remote states. We introduce the $\delta$-CRDT framework, and we explain it through establishing a correspondence to current state-based CRDTs. In addition, we present an anti-entropy algorithm for eventual convergence, and another one that ensures causal consistency. Finally, we introduce several $\delta$-CRDT specifications of both well-known replicated datatypes and novel datatypes, including a generic map composition.
1 Introduction
State-based CRDTs tolerate unreliable dissemination but can incur high communication costs by shipping entire states, while operation-based CRDTs rely on reliable exactly-once causal broadcast. The paper introduces δ-CRDTs, which ship incremental states and give conditions and algorithms for eventual and causal consistency.
1 Introduction
- State-based CRDT communication can become costly as states grow, while operation-based CRDTs require reliable exactly-once causal broadcast and coordinated membership.Operation-based systems also execute operations individually at each node; the paper identifies large sets and maps as cases where state size is a concern.Source: §1 · p. 2
- δ-mutators return deltas representing recent updates, which replicas incorporate by joining with their local states instead of shipping the entire state.Deltas may be retained and shipped individually or joined in groups.Source: §1 · p. 2
- Individual deltas are state fragments, so causal merging is needed to preserve the intended semantics; the paper presents a causal delta-merging condition and algorithm.The algorithm sends delta-intervals whose joining has the same effect as shipping and joining the entire state.Source: §1 · p. 3
- The framework relates δ-mutators to original CRDT mutators and establishes conditions under which delivered and joined deltas guarantee eventual consistency.The paper also presents an anti-entropy algorithm for eventual convergence.Source: §1 · p. 3
- The paper illustrates δ-CRDTs with a counter, then presents specifications adapting known designs and a generic framework for causal CRDTs and composable maps.The authors report that adapting existing CRDTs takes design effort that varies with their complexity; new datatypes can instead be written with delta-mutators.Source: §1 · p. 3
2 System Model
The system model assumes asynchronous communication that can lose, duplicate, or reorder messages, but that eventually delivers some messages when transmission continues. Its notation covers maps, pairs, number sets, partial functions, and bottom elements.
2 System Model
- The model has no shared memory or global clock, and places no bounds on message delay or relative processing speeds.Messages may be lost, duplicated, or reordered, but are not corrupted; infinitely repeated sending yields infinitely many deliveries.Source: §2 · p. 3
- Nodes can crash and recover from durable storage, with each state transition written atomically; each node has a globally unique identifier.Partitions may be arbitrarily long but eventually heal under the message-delivery assumption.Source: §2 · p. 3
2.1 Notation
- The notation treats maps as key-value pairs and uses ⊥ for a set's least element; an unmapped key denotes the codomain's bottom when one exists.The passage also defines map domain and range, pair projections, and notation for booleans, natural numbers, integers, and node identifiers.Source: §2.1 · p. 4
3 A Background of State-based CRDTs
State-based CRDTs converge by propagating full states and merging them with a join, but that communication can be wasteful when updates change only a small part of a large state. Their join structure supports convergence despite unreliable message delivery.
3 A Background of State-based CRDTs
- State-based CRDTs propagate local states and merge received states using a join that returns their least upper bound in a join-semilattice.The join is commutative, associative, and idempotent.Source: §3 · p. 4
- Mutators produce monotonic state sequences, and replicas converge to the join of their states when mutations stop and anti-entropy proceeds.Anti-entropy periodically ships entire local states, which replicas merge with their own states.Source: §3 · p. 4
- State-based CRDTs tolerate message loss, duplication, reordering, and temporary partitions without compromising availability or eventual convergence.The model relies on anti-entropy proceeding after mutations stop.Source: §3 · pp. 4–5
- In the increment-only counter, each replica stores a map of replica identifiers to counts, increments its own entry, sums entries for queries, and joins maps by pointwise maximum.The figure is identified as a state-based counter CRDT.Source: §3 · p. 5, Figure 1 · p. 5
- Full-state dissemination can be costly: a counter sends its whole replica map even when an increment changes only the local replica's entry.For grow-only sets, state size grows with the set; the passage identifies large sets and composable maps as cases that strain full-state shipping.Source: §3 · p. 5
4 Delta-state CRDTs
Delta-state CRDTs represent updates as joinable delta-states rather than requiring every update to ship the resulting full state. The paper relates these delta-mutators to standard CRDT mutators and illustrates the smaller payload with a counter.
4 Delta-state CRDTs
- A δ-CRDT is a state-based CRDT whose delta-mutators return delta-states in the same join-semilattice, and replicas join those deltas into their current state.Deltas may be combined into delta-groups and sent later; a full state is an extreme case of a delta-group.Source: §4 · pp. 5–6
4.2 Example: δ-CRDT Counter
- Because each delta is a state joined with the current state, it can be re-joined without exactly-once delivery; combining deltas can also collapse multiple increments.When causal order is unimportant, delta-groups may use unreliable dissemination that drops, reorders, or duplicates messages.Source: §4 · p. 6, §4.2 · p. 8
4.1 Delta-state decomposition of standard CRDTs
- A δ-CRDT decomposes a standard CRDT when joining each corresponding delta-mutator’s output with the current state gives the standard mutator’s transition.The framework seeks non-trivial decompositions whose delta-states are smaller than the resulting state; minimal deltas avoid information already present in the input state.Source: §4.1 · pp. 6–7
4.2 Example: δ-CRDT Counter
- A counter delta-mutator returns only the updated local replica’s map entry, preserving the counter’s semantics while allowing smaller payloads than the full map.Multiple increments can be joined into one delta-group, reducing communication overhead.Source: §4.2 · pp. 7–8, Figure 2 · p. 8
5 State Convergence
The paper establishes eventual convergence when every generated delta-mutation reaches every replica. Its basic anti-entropy algorithm buffers and periodically disseminates delta-groups or full states.
5 State Convergence
- If every delta-mutation reaches every other replica, directly or within a delta-group, all replica states become equal.The result follows from join being associative, commutative, and idempotent.Source: §5 · p. 8
- The basic algorithm can target eventual convergence without causal consistency, allowing a trade-off between performance and consistency guarantees.The paper gives a counter as an example where not losing increments and achieving convergence may suffice.Source: §5 · p. 8, §5.1 · p. 9
5.1 Basic Anti-Entropy Algorithm
- The basic algorithm periodically sends a buffered delta-group or full state, and joins each received payload into the local state.A received delta-group may also be buffered for transitive propagation, or deltas may be sent directly from their originating replica.Source: §5.1 · p. 9
6 Causal Consistency
The paper gives a condition for joining delta-intervals that preserves the outcomes of standard state-based CRDTs. It then describes an anti-entropy algorithm satisfying that condition to ensure causal consistency.
6 Causal Consistency
- The causal delta-merging condition permits joining an interval only into a state that subsumes the state where the interval’s first delta was previously joined.This condition makes the delta-interval algorithm’s outcome equivalent to that of a standard CRDT.Source: §6 · p. 10
- A δ-CRDT using delta-interval anti-entropy that satisfies the causal delta-merging condition ensures causal consistency.Under that condition, reachable δ-CRDT states correspond to states reachable in the standard state-based CRDT.Source: §6 · pp. 10–11
6.1 Anti-Entropy Algorithm for Causal Consistency
- The causal-consistency algorithm sends each neighbor appropriate delta-intervals and uses acknowledgments to track joined intervals and handle duplicates or out-of-order messages.It sends the full state when the needed deltas are unavailable or the delta sequence is empty; old deltas are garbage-collected after all neighbors acknowledge them.Source: §6.1 · pp. 12–13
- The algorithm produces the same reachable states as a standard CRDT algorithm, ensuring causal consistency.The node keeps its counter in durable storage so a delayed acknowledgment after recovery cannot cause it to skip deltas and violate the merging condition.Source: §6.1 · pp. 12–13
7 Portfolio of δ-CRDTs
The portfolio applies delta-mutators to simple compositions, anonymous and named CRDTs, and causal CRDTs, including a map that embeds causal datatypes. It is illustrative rather than exhaustive, and standard mutators can be obtained by composing delta-mutators with join.
7 Portfolio of δ-CRDTs
- The portfolio illustrates delta-based specifications for several CRDTs rather than surveying them exhaustively, and delta-mutators can also serve as building blocks for standard mutators.The portfolio covers simple compositions, anonymous and named CRDTs, and causal CRDTs.Source: §7 · p. 13
7.1 Simple Lattice Compositions
- Pair composition joins components coordinate-wise, while lexicographic composition gives the first component priority and joins the second only on a tie.A total order in the first component can make the outcome depend on timestamps.Source: §7.1 · p. 14
7.2 Anonymous δ-CRDTs
- Anonymous δ-CRDTs include a grow-only set whose insert delta contains only the new element, a two-phase set that forbids re-adding removed elements, and a timestamped set where later timestamps win and adds win ties.The timestamped set relies on clients to supply monotonically increasing timestamps.Source: §7.2 · pp. 15–16
7.3 Named δ-CRDTs
- Named δ-CRDTs include a positive-negative counter that subtracts decrements from increments and a lexicographic counter whose decrements raise the first component so the updated pair wins joins.Named CRDT mutations use the replica identifier.Source: §7.3 · pp. 16–17
7.4 Causal δ-CRDTs
- Causal CRDTs pair a dot store with a causal context, enabling flags, registers, sets, and maps; a shared context lets maps embed causal CRDTs, including recursively.The map can remove keys by removing dots in embedded values, without a per-key causal context.Source: §7.4 · pp. 18, 23
8 Related Work
Related work situates CRDTs among approaches to eventual convergence, then contrasts ways of reducing message size and encoding causal histories. The discussion distinguishes δ-CRDTs from prior delta and operation-based approaches by their framework and dissemination trade-offs.
8.1 Eventually convergent data types.
- CRDTs formalize eventually convergent replicated data types, alongside related approaches including BloomL, Cloud Types, and LVars.LVars use state join-semilattices for deterministic parallel programming, with access limited to special threshold reads.Source: §8.1 · p. 24
8.2 Message size.
- δ-CRDTs use small deltas for message-size reduction and coalescing, unlike prior delta methods that require extra merges or multi-step protocols.Pure operation-based CRDTs also use compact messages but require stronger delivery and membership guarantees; a globally stable operation log can require more coordination and stall dissemination.Source: §8.2 · p. 24
8.3 Encoding causal histories.
- Because δ-CRDT deltas and delta-groups are normally not causally consistent, their metadata and anti-entropy must handle histories that version vectors cannot always summarize.Concise Version Vectors and Interval Version Vectors encode gaps; Interval Version Vectors optimize sequences while retaining efficiency when gaps are absent.Source: §8.3 · pp. 24–25
9 Conclusion
The paper introduces δ-CRDTs, whose delta-mutators capture update effects for shipping as small states while preserving standard state-based CRDT properties. It also presents causal-consistency and anti-entropy techniques, and describes how the approach can replace state-based CRDTs or mimic operation-based behavior with weaker dissemination guarantees.
9 Conclusion
- Delta-mutators detach operation-induced changes from state-based datatypes, enabling small deltas to be shipped instead of entire states while preserving idempotence, associativity, and commutativity.The paper also presents an anti-entropy algorithm for replacing classical state-based CRDTs with more efficient ones while preserving their properties.Source: §9 · p. 25
- δ-CRDTs achieve causal consistency and include novel specifications, a general framework for causal CRDTs, and composition in maps.Source: §9 · p. 25
- δ-CRDTs can replace classical state-based CRDTs without losing their power and can mimic operation-based behavior by shipping individual deltas with weaker dissemination guarantees.Source: §9 · p. 25