{'fraction_non_alphanumeric': 0.038351980735911666, 'fraction_numerical': 0.0029953308078583384, 'mean_word_length': 4.658690594882021, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficient State-based CRDTs by Delta-Mutation

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 en- tire 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 Datatypes ({\delta}-CRDT) 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 is joined to 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 that ensures causal consistency, and we introduce two {\delta}-CRDT specifications of well-known replicated datatypes.


Introduction
Eventual consistency (EC) is a relaxed consistency model that is often adopted by large-scale distributed systems [1,2,3] where availability must be maintained, despite outages and partitioning, whereas delayed consistency is acceptable. The limitations resulting from the CAP theorem [4] suggest trading strong consistency for high availability. A typical approach in EC systems is to allow replicas of a distributed object to temporarily diverge, provided that they can eventually be reconciled into a common state. To avoid application-specific reconciliation methods, costly and error-prone, Conflict-Free Replicated Data Types (CRDTs) [5,6] were introduced, allowing the design of self-contained distributed data types that are always available and eventually converge when all operations are reflected at all replicas. Though CRDTs are being deployed in practice [1], more work is still required to improve their design and performance.
CRDTs support two complementary designs: state-based which disseminate object states and operation-based which disseminate operations [5,6]. In a statebased design [7,6] an operation is only executed on the local replica state. A replica periodically propagates its local changes to other replicas through shipping its entire state. A received state is incorporated with the local state via a merge function that deterministically reconciles both states. To maintain convergence, merge is defined as a join: a least upper bound over a join-semilattice [7,6].
A major drawback in current state-based CRDTs is the communication overhead of shipping the entire state, which can get very large in size. For instance, the state size of a counter CRDT (a vector of integer counters, one per replica) increases with the number of replicas; whereas in a grow-only Set, the state size depends on the set size, that grows as more operations are invoked. This communication overhead limits the use of state-based CRDTs to data-types with small state size (e.g., counters are reasonable while sets are not); recently there has been demand for CRDTs with large state sizes (e.g., in RIAK DT Maps [8] that can compose multiple CRDTs).
In this paper, we rethink the way state-based CRDTs should be designed, having in mind the problematic shipping of the entire state. Our aim is to ship a representation of the effect of recent update operations on the state, rather than the whole state, while preserving the idempotent nature of join; thus, allowing unreliable communication, on the contrary to operation-based CRDTs that demand exactly-once delivery and are prone to message replays. To achieve this, we introduce Delta State-based CRDTs (δ-CRDT): a state is a join-semilattice that results from the join of multiple fine-grained states, i.e., deltas, generated by what we call δ-mutators; these are new versions of the datatype mutators that return the effect of these mutators on the state. In this way, deltas can be retained in a buffer to be shipped individually (or joined in groups) instead of shipping the entire object. The changes to the local state are then incorporated at other replicas by joining the shipped deltas with their own states.
A key point in our approach is a simple equation relating the novel δ-mutators with the original CRDT mutators. The challenge when designing a new δ-CRDT that corresponds to an existing CRDT is to derive δ-mutators that obey this equation. In this paper, we prove that eventual consistency is guaranteed in δ-CRDT as long as all deltas produced by δ-mutators are delivered and joined at other replicas, and we present a corresponding simple anti-entropy algorithm. We then focus on causal consistency, introducing the concept of delta-interval and the causal delta-merging condition. Based on these, we then present an antientropy algorithm for δ-CRDT, where sending and then joining delta-intervals into another replica state produces the same effect as if the entire state had been shipped and joined. We illustrate our approach by explaining a simple counter δ-CRDT specification; and then we introduce a challenging non-trivial specification for a widely used datatype: Optimized Add-Wins Observed-Remove Sets. In addition, we make a basic δ-CRDT C++ library available online [9] for various CRDTs. Our experience shows that a δ-CRDT version can be devised for any CRDT, however, this requires some design effort that varies with the complexity of different CRDTs.

System Model
Consider a distributed system with nodes containing local memory, with no shared memory between them. Any node can send messages to any other node. The network is asynchronous, there being no global clock, no bound on the time it takes for a message to arrive, nor bounds on relative processing speeds. The network is unreliable: messages can be lost, duplicated or reordered (but are not corrupted). Some messages will, however, eventually get through: if a node sends infinitely many messages to another node, infinitely many of these will be delivered. In particular, this means that there can be arbitrarily long partitions, but these will eventually heal. Nodes have access to durable storage; nodes can crash but eventually will recover with the content of the durable storage as at the time of the crash. Durable state is written atomically at each state transition. Each node has access to its globally unique identifier in a set I.

A Background of State-based CRDTs
Conflict-Free Replicated Data Types [5,6] (CRDTs) are distributed datatypes that allow different replicas of a distributed CRDT instance to diverge and ensures that, eventually, all replicas converge to the same state. State-based CRDTs achieve this through propagating updates of the local state by disseminating the entire state across replicas. The received states are then merged to remote states, leading to convergence.
A state-based CRDT consists of a triple (S, M, Q), where S is a join-semilattice [10], Q is a set of query functions (which return some result without modifying the state), and M is a set of mutators that perform updates; a mutator m ∈ M takes a state X ∈ S as input and returns a new state X = m(X). A join-semilattice is a set with a partial order and a binary join operation that returns the least upper bound (LUB) of two elements in S; a join is designed to be commutative, associative, and idempotent. Mutators are defined in such a way to be inflations, i.e., for any mutator m and state X, the following holds: In this way, for each replica there is a monotonic sequence of states, defined under the lattice partial order, where each subsequent state subsumes the previous state when joined elsewhere.
Both query and mutator operations are always available since they are performed using the local state without requiring inter-replica communication; however, as mutators are concurrently applied at distinct replicas, replica states will likely diverge. Eventual convergence is then obtained using an anti-entropy protocol that periodically ships the entire local state to other replicas. Each replica merges the received state with its local state using the join operation in S. Given the mathematical properties of join, if mutators stop being issued, all replicas eventually converge to the same state. i.e. the least upper-bound of all states involved. State-based CRDTs are interesting as they demand little guarantees from the dissemination layer, working under message loss, duplication, reordering, and temporary network partitioning, without impacting availability and eventual convergence.   1 represents a state-based increment-only counter. The CRDT state Σ is a map from replica identifiers to positive integers. Initially, σ 0 i is an empty map (assuming that unmapped keys implicitly map to zero, and only non zero mappings are stored). A single mutator, i.e., inc, is defined that increments the value corresponding to the local replica i (returning the updated map). The query operation value returns the counter value by adding the integers in the map entries. The join of two states is the point-wise maximum of the maps. The main weakness of state-based CRDTs is the cost of dissemination of updates, as the full state is sent. In this simple example of counters, even though increments only update the value corresponding to the local replica i, the whole map will always be sent in messages though the other map values remained intact (since no messages have been received and merged).
It would be interesting to only ship the recent modification incurred on the state. This is, however, not possible with the current model of state-based CRDTs as mutators always return a full state. Approaches which simply ship operations (e.g., an "increment n" message), like in operation-based CRDTs, require reliable communication (e.g., because increment is not idempotent). In contrast, our approach allows producing and encoding recent mutations in an incremental way, while keeping the advantages of the state-based approach, namely the idempotent, associative, and commutative properties of join.

Delta-state CRDTs
We introduce Delta-State Conflict-Free Replicated Data Types, or δ-CRDT for short, as a new kind of state-based CRDTs, in which delta-mutators are defined to return a delta-state: a value in the same join-semilattice which represents the updates induced by the mutator on the current state.
Definition 1 (Delta-mutator). A delta-mutator m δ is a function, corresponding to an update operation, which takes a state X in a join-semilattice S as parameter and returns a delta-mutation m δ (X), also in S.

Definition 3 (δ-CRDT).
A δ-CRDT consists of a triple (S, M δ , Q), where S is a join-semilattice, M δ is a set of delta-mutators, and Q a set of query functions, where the state transition at each replica is given by either joining the current state X ∈ S with a delta-mutation: or joining the current state with some received delta-group D: In a δ-CRDT, the effect of applying a mutation, represented by a deltamutation δ = m δ (X), is decoupled from the resulting state X = X δ, which allows shipping this δ rather than the entire resulting state X . All state transitions in a δ-CRDT, even upon applying mutations locally, are the result of some join with the current state. Unlike standard CRDT mutators, delta-mutators do not need to be inflations in order to inflate a state; this is however ensured by joining their output, i.e., deltas, into the current state.
In principle, a delta could be shipped immediately to remote replicas once applied locally. For efficiency reasons, multiple deltas returned by applying several delta-mutators can be joined locally into a delta-group and retained in a buffer. The delta-group can then be shipped to remote replicas to be joined with their local states. Received delta-groups can optionally be joined into their buffered delta-group, allowing transitive propagation of deltas. A full state can be seen as a special (extreme) case of a delta-group.
If the causal order of operations is not important and the attended aim is merely eventual convergence of states, then delta-groups can be shipped using an unreliable dissemination layer that may drop, reorder, or duplicate messages. Delta-groups can always be re-transmitted and re-joined, possibly out of order, or can simply be subsumed by a less frequent sending of the full state, e.g. for performance reasons or when doing state transfers to new members. In Section 4, we address state convergence when causal consistency is not required, and we address the latter in Section 5.

Delta-state decomposition of standard CRDTs
, if for every mutator m ∈ M , we have a corresponding mutator m δ ∈ M δ such that, for every state X ∈ S: This equation states that applying a delta-mutator and joining into the current state should produce the same state transition as applying the corresponding mutator of the standard CRDT.
Given an existing state-based CRDT (which is always a trivial decomposition of itself, i.e., m(X) = X m(X), as mutators are inflations), it will be useful to find a non-trivial decomposition such that delta-states returned by deltamutators in M δ are smaller than the resulting state:   2 depicts a δ-CRDT specification of a counter datatype that is a deltastate decomposition of the state-based counter in Fig. 1. The state, join and value query operation remain as before. Only the mutator inc δ is newly defined, which increments the map entry corresponding to the local replica and only returns that entry, instead of the full map as inc in the state-based CRDT counter does. This maintains the original semantics of the counter while allowing the smaller deltas returned by the delta-mutator to be sent, instead of the full map. As before, the received payload (whether one or more deltas) might not include entries for all keys in I, which are assumed to have zero values. The decomposition is easy to understand in this example since the equation inc i (X) = X inc δ i (X) holds as m{i → m(i) + 1} = m {i → m(i) + 1}. In other words, the single value for key i in the delta, corresponding to the local replica identifier, will overwrite the corresponding one in m since the former maps to a higher value (i.e., using max). Here it can be noticed that: (1) a delta is just a state, that can be joined possibly several times without requiring exactly-once delivery, and without being a representation of the "increment" operation (as in operation-based CRDTs), which is itself non-idempotent; (2) joining deltas into a delta-group and disseminating delta-groups at a lower rate than the operation rate reduces data communication overhead, since multiple increments from a given source can be collapsed into a single state counter.

State Convergence
In the δ-CRDT execution model, and regardless of the anti-entropy algorithm used, a replica state always evolves by joining the current state with some delta: either the result of a delta-mutation, or some arbitrary delta-group (which itself can be expressed as a join of delta-mutations). Therefore, all states can be expressed as joins of delta-mutations, which makes state convergence in δ-CRDT easy to achieve: it is enough that all delta-mutations generated in the system reach every replica, as expressed by the following proposition. Proposition 1. (δ-CRDT convergence) Consider a set of replicas of a δ-CRDT object, replica i evolving along a sequence of states X 0 i = ⊥, X 1 i , . . ., each replica performing delta-mutations of the form m δ i,k (X k i ) at some subset of its sequence of states, and evolving by joining the current state either with self-generated deltas or with delta-groups received from others. If each delta-mutation m δ i,k (X k i ) produced at each replica is joined (directly or as part of a delta-group) at least once with every other replica, all replica states become equal.
Proof. Trivial, given the associativity, commutativity, and idempotence of the join operation in any join-semilattice.
This opens up the possibility of having anti-entropy algorithms that are only devoted to enforce convergence, without necessarily providing causal consistency (enforced in standard CRDTs); thus, making a trade-off between performance and consistency guarantees. For instance, in a counter (e.g., for the number of likes on a social network), it may not be critical to have causal consistency, but merely not to lose increments and achieve convergence.

Basic Anti-Entropy Algorithm
A basic anti-entropy algorithm that ensures eventual convergence in δ-CRDT is presented in Algorithm 1. For the node corresponding to replica i, the durable state, which persists after a crash, is simply the δ-CRDT state X i . The volatile state D stores a delta-group that is used to accumulate deltas before eventually sending it to other replicas. Without loss of generality, we assume that the joinsemilattice has a bottom ⊥, which is the initial value for both X i and D i .
When an operation is performed, the corresponding delta-mutator m δ is applied to the current state of X i , generating a delta d. This delta is joined both with X i to produce a new state, and with D. In the same spirit of standard state based CRDTs, a node sends its messages in a periodic fashion, where the message payload is either the delta-group D i or the full state X i ; this decision is made by the function choose i which returns one of them. To keep the algorithm simple, a node simply broadcasts its messages without distinguishing between neighbors. After each send, the delta-group is reset to ⊥.
Once a message is received, the payload d is joined into the current δ-CRDT state. The basic algorithm operates in two modes: (1) a transitive mode (when t i is true) in which m is also joined into D, allowing transitive propagation of delta-mutations; meaning that, deltas received at node i from some node j can later be sent to some other node k; (2) a direct mode where a delta-group is exclusively the join of local delta-mutations (j must send its deltas directly to k). The decisions of whether to send a delta-group versus the full state (typically less periodically), and whether to use the transitive or direct mode are out of the scope of this paper. In general, decisions can be made considering many criteria like delta-groups size, state size, message loss distribution assumptions, and network topology.

Causal Consistency
For some CRDTs with commutative operations, like the counter in Fig. 2 , eventual convergence of states may be enough, and thus any anti-entropy algorithm that satisfies the condition in Proposition 1, like Algorithm 1, can be used. However, stronger consistency guarantees, like causal consistency, are often required by today's applications. When using an anti-entropy mechanism which disseminates deltas with no order guarantees (like Algorithm 1) the execution is, in general, not causally consistent.
Traditional state-based CRDTs converge using joins of the full state, which implicitly ensures per-object causal consistency [11]: each state of some replica of an object reflects the causal past of operations on the object (either applied locally, or applied at other replicas and transitively joined).
Therefore, it is desirable to have δ-CRDTs offer the same causal-consistency guarantees that standard state-based CRDTs offer. This raises the question about how can delta propagation and merging of δ-CRDT be constrained (and expressed in an anti-entropy algorithm) in such a manner to give the same results as if a standard state-based CRDT was used. Towards this objective, it is useful to define a particular kind of delta-group, which we call a delta-interval : Definition 4 (Delta-interval). Given a replica i progressing along the states X 0 i , X 1 i , . . ., by joining delta d k i (either local delta-mutation or received deltagroup) into X k i to obtain X k+1 i , a delta-interval ∆ a,b i is a delta-group resulting from joining deltas d a i , . . . , The use of delta-intervals in anti-entropy algorithms will be a key ingredient towards achieving causal consistency. We now define a restricted kind of antientropy algorithms for δ-CRDTs.
Definition 5 (Delta-interval-based anti-entropy algorithm). A given antientropy algorithm for δ-CRDTs is delta-interval-based, if all deltas sent to other replicas are delta-intervals.
Moreover, to achieve causal consistency the next condition must satisfied: Definition 6 (Causal delta-merging condition). A delta-interval based antientropy algorithm is said to satisfy the causal delta-merging condition if the algorithm only joins ∆ a,b j from replica j into replica i states X i that satisfy: This means that a delta-interval is only joined into states that at least reflect (i.e., subsume) the state into which the first delta in the interval was previously joined. The causal delta-merging condition is important since any delta-interval based anti-entropy algorithm of a δ-CRDT that satisfies it, can be used to obtain the same outcome of standard CRDTs; this is formally stated in Proposition 2.
Proposition 2. (CRDT and δ-CRDT correspondence) Let (S, M, Q) be a standard state-based CRDT and (S, M δ , Q) a corresponding delta-state decomposition. Any δ-CRDT state reachable by an execution E δ over (S, M δ , Q), by a delta-interval based anti-entropy algorithm A δ satisfying the causal delta-merging condition, is equal to a state resulting from an execution E over (S, M, Q), having the corresponding data-type operations, by an anti-entropy algorithm A for state-based CRDTs.
Proof. See appendix. Corollary 1. (δ-CRDT causal consistency) Any δ-CRDT in which states are propagated and joined using a delta-interval-based anti-entropy algorithm satisfying the causal delta-merging condition ensures causal consistency.
Proof. From Proposition 2 and causal consistency of state-based CRDTs.

Anti-Entropy Algorithm for Causal Consistency
Algorithm 2 is a delta-interval based anti-entropy algorithm which enforces the causal delta-merging condition. It can be used whenever the causal consistency guarantees of standard state-based CRDTs are needed. For simplicity, it excludes some optimizations that are important, but easy to derive, in practice. The algorithm distinguishes neighbor nodes, and only sends them delta-intervals that are joined at the receiving node, obeying the delta-merging condition.
Each node i keeps a contiguous sequence of deltas d l i , . . . , d u i in a map D from integers to deltas, with l = min(dom(M )) and u = max(dom(M )). The sequence numbers of deltas are obtained from the counter c i that is incremented when a delta (whether a delta-mutation or delta-interval received) is joined with the current state. Each node i keeps an acknowledgments map A that stores, for each neighbor j, the index b such that ∆ a,b i is the last delta-interval acknowledged by j (after it receives ∆ a,b i from i and joins it into X j ).
Node i sends a delta-interval d = ∆ a,b i with a (delta, d, b) message; the receiving node j, after joining ∆ a,b i into its replica state, replies with an acknowledgment message (ack, b); if an ack from j was successfully received by node i, it updates the entry of j in the acknowledgment map, using the max function. This handles possible old duplicates and messages arriving out of order.
Like the δ-CRDT state, the counter c i is also kept in a durable storage. This is essential to avoid conflicts after potential crash and recovery incidents. Otherwise, there would be the danger of receiving some delayed ack, for a deltainterval sent before crashing, make the node skip sending some deltas generated after recovery, thus violating the delta-merging condition.
The algorithm for node i periodically picks a random neighbor j. In principle, i sends the join of all deltas starting from the delta that j acked and forward. Exceptionally, i sends the entire state in two cases: (1) if the sequence of deltas D i is empty, or (2) if j is expecting from i a delta that was already removed from D i (e.g., after a crash and recovery); i tracks this in A i [j]. To garbage collect old deltas, the algorithm periodically removes the deltas that have been acked by all neighbors.  Proof. See appendix.

δ-CRDTs for Add-Wins OR-Sets
An Add-wins Observed-Remove Set is a well-known CRDT datatype that offers the same sequential semantics of a sequential set and adopts a specific resolution semantics for operations that concurrently add and remove the same element. Add-wins means that an add prevails over a concurrent remove. Remove operations, however, only affect elements added by causally preceding adds. Fig. 3a depicts a simple, but inefficient, δ-CRDT implementation of a statebased add-wins OR-Set. The state Σ consists of a set of tagged elements and a set of tags, acting as tombstones. Globally unique tags of the form I×N are used and ensured by pairing a replica identifier in I with a monotonically increasing natural counter. Once an element e ∈ E is added to the set, the delta-mutator add δ creates a globally unique tag by incrementing the highest tag present in its local state and that was created by replica i itself (max returns 0 if no tag is present). This tag is paired with value e and stored as a new unique triple. Since removes should only tombstone elements that are added before the remove operation, the delta-mutator rmv δ retains in the tombstone set all tags associated to element e, being removed from the local state. Function elements only returns the elements that are added but not tombstoned yet. Join simply unions the respective sets that are, therefore, both grow-only.
A more efficient design is presented in Fig. 3b, which offers the same semantics and have a similar state structure; however, it uses a different join-semilattice, allowing the set of tagged elements to shrink as elements are removed. Now, elements returns all elements in the tagged set s. Instead of the tombstone set, a causal context set is used. Adding an element creates a unique tag by resorting to the causal context c instead of s, that can now shrink; the new triple is added to s as before, but now the new tag is also added to causal context c. The deltamutator rmv δ is the same as before, collecting all tags associated to the element being removed. The desired semantics are achieved by the novel join operation . To join two states, their causal contexts are simply unioned; whereas, the new tagged element set only preserves: (1) the triples present in both sets (therefore, not removed in either), and also (2) any triple present in one of the sets and whose tag is not present in the causal context of the other state.
Causal Context Compression. For presentation simplicity, this optimized version of the add-wins OR-Set has a grow-only causal context that collects all the unique tags (even from elements added but no longer present). In practice the causal context can be efficiently compressed without any loss of information. When using an anti-entropy algorithm that provides causal consistency, e.g., Algorithm 2, then for each replica state X i = (s i , c i ) and replica identifier j ∈ I, we have a contiguous sequence: Thus, the causal context can always be encoded as a compact version vector [12] I → N that keeps the maximum sequence number for each replica. Even under non-causal anti-entropy, compression is still possible by keeping a version vector that encodes the offset of the contiguous sequence of tags from each replica, together with a set for the non-contiguous tags. As anti-entropy proceeds, each tag is eventually encoded in the vector, and thus the set remains typically small. Compression is less likely for the causal context of delta-groups in transit or buffered to be sent, but those contexts are only transient and smaller than those in the actual replica states. Moreover, the same techniques that encode contiguous sequences of tags can also be used for transient context compression [13].

Message Complexity
Our delta-based framework, δ-CRDT, clearly introduces significant cost improvements on messaging. Despite being generic, δ-CRDT requires deltas to be defined per datatype. This makes the bit-message complexity datatype-based rather than generic. To give an intuition about this complexity, we address the two datatypes introduced above: counter and OR-Set. In classical state-based counter CRDTs, the entire map of the counter is shipped. As the map-size grows with the number of replicas, this leads a bit-message complexity of O(|I|) 1 . Whereas, in the δ-CRDT case, only recently updated map entries α are shipped yielding a bitcomplexity O(α), where α |I|. Moreover, if transitive forwarding is not allowed this drops to constant O(1). As for OR-set, shipping in classical OR-set CRDTs delivers the entire state which yields a bit-message complexity of O(S), where S is the state-size. In δ-CRDT, only deltas are shipped, which renders a bit-message complexity O(s) where s represents the size of the recent updates occurred since the last shipping. Clearly, s S since the updates that occur on a state in a period of time are often much less than the total number of items.

Related Work
Eventually convergent data types. The design of replicated systems that are always available and eventually converge can be traced back to historical designs in [14,15], among others. More recently, replicated data types that always eventually converge, both by reliably broadcasting operations (called operationbased) or gossiping and merging states (called state-based), have been formalized as CRDTs [16,7,5,6]. These are also closely related to Bloom L [17] and Cloud Types [18]. State semi-lattices were used for deterministic parallel programming in LVars [19], where variables progress in the lattice order by joining other values, and are only accessible by special threshold reads.

Message size.
A key feature of δ-CRDT is message size reduction and coalescing, using small-sized deltas. The general old idea of using differences between things, called "deltas" in many contexts, can lead to many designs, depending on how exactly a delta is defined. The state-based deltas introduced for Computational CRDTs [20] require an extra delta-specific merge which does not ensure idempotence. In [21], an improved synchronization method for non-optimized OR-set CRDT [5] is presented, where delta information is propagated; in that paper deltas are a collection of items (related to update events between synchronizations), manipulated and merged through a protocol, as opposed to normal states in the semilattice. No generic framework is defined (that could encompass other data types) and the protocol requires several communication steps to compute the information to exchange. Operation-based CRDTs [5,6,22] also support small message sizes, and in particular, pure flavors [22] that restrict messages to the operation name, and possible arguments. Though pure operation-based CRDTs allow for compact states and are very fast at the source (since operations are broadcast without consulting the local state), the model requires more systems guarantees than δ-CRDT do, e.g., exactly-once reliable delivery and membership information, and impose more complex integration of new replicas.
Encoding causal histories. State-based CRDT are always designed to be causally consistent [7,6]. Optimized implementations of sets, maps, and multi-value registers can build on this assumption to keep the meta-data small [11]. In δ-CRDT, however, deltas and delta-groups are normally not causally consistent, and thus the design of join, the meta-data state, as well as the anti-entropy algorithm used must ensure this. Without causal consistency, the causal context in δ-CRDT can not always be summarized with version vectors, and consequently, techniques that allow for gaps are often used. A well known mechanism that allows for encoding of gaps is found in Concise Version Vectors [23]. Interval Version Vec-tors [13], later on, introduced an encoding that optimizes sequences and allows gaps, while preserving efficiency when gaps are absent.

Conclusion
CRDTs allow flexible, while principled, design of distributed protocols that trade strict consistency for improved availability, faster response time, and support for disconnected operation. These benefits are harvested once a given application can model all, or a part, of its behavior using CRDTs. In particular, state-based CRDTs allow idempotent gossiping of states and require very basic guarantees from the network, as they cope with message loss, re-ordering, and duplication.
State-based CRDTs come with a price: states have a potential to get very large. This is even worse if multiple objects are composed into a single CRDT object to benefit from intra-replica consistency and atomicity. In this paper, we addressed these limitations by introducing the new concept of δ-CRDT. By devising delta-mutators over state-based datatypes which can detach the changes that an operation induces on the state. This brings a significant performance gain as it allows only shipping small states, i.e., deltas, instead of the entire state. The significant property in δ-CRDT is that it preserves the crucial properties (idempotence, associativity and commutativity) of standard state-based CRDT.
We have shown how δ-CRDT can achieve convergence possibly with, or without, causal consistency; and we presented an anti-entropy algorithm for each case. In particular, the causally consistent algorithm allows replacing classical state-based CRDTs by more efficient ones, while preserving their properties. As a first application of our approach, we designed a novel δ-CRDT specification for a well-known and widely used datatype: an optimized observed-remove set.