📖Delta State Replicated Data Types

Almeida, Paulo S'ergio and Shoker, Ali and Baquero, Carlos
  • I think most of these data structures are available in Riak via riakdt
  • Excerpts:
    • Instead of shipping the whole state, ship only deltas (δ-state) generated by δ-mutators.
    • Definition 1 (Delta-mutator). A delta-mutator mδm^δ is a function, corresponding to an update operation, which takes a state XX in a join-semilattice SS as parameter and returns a delta-mutation mδ(X)m^δ(X), also in SS.
    • Definition 2 (Delta-group). A delta-group is inductively defined as either a delta-mutation or a join of several delta-groups.
    • Definition 3 (δ-CRDT). A δ-CRDT consists of a triple (S,Mδ,Q)(S, M^δ, Q), where SS is a join-semilattice, MδM^δ is a set of delta-mutators, and QQ a set of query functions, where the state transition at each replica is given by either joining the current state X∈SX ∈ S with a delta-mutation: X′=X⊔mδ(X)X' = X ⊔ m^δ(X), or joining the current state with some received delta-group DD: X′=X⊔DX' = X ⊔ D.
    • it will be useful to find a non-trivial decomposition such that delta-states returned by delta-mutators in MδM^δ are smaller than the resulting state: size(mδ(X))≪size(m(X))size(m^δ(X))≪size(m(X))
    • Definition 4 (Delta-interval). Given a replica ii progressing along the states Xi0,Xi1,...X^0_i, X^1_i, . . ., by joining delta dikd^k_i (either local delta-mutation or received delta-group) into XikX^k_i to obtain Xik+1X^{k+1}_i, a delta-interval Δia,b\Delta^{a,b}_i is a delta-group resulting from joining deltas dia,...,dib−1d^a_i, . . . , d^{b-1}_i: Δia,b=⊔{dik∣a≤k<b}\Delta^{a,b}_i=⊔\{d^k_i | a ≤ k < b\}
    • Definition 5 (Delta-interval-based anti-entropy algorithm). A given anti-entropy algorithm for δ-CRDTs is delta-interval-based, if all deltas sent to other replicas are delta-intervals.
    • Definition 6 (Causal delta-merging condition). A delta-interval based anti-entropy algorithm is said to satisfy the causal delta-merging condition if the algorithm only joins Δja,b\Delta^{a,b}_j from replica jj into state XiX_i of replica ii that satisfy: Xi⊒XjaX_i ⊒ X^a_j
    • Portfolios contains the following data types:
      • G-Set
      • 2P-Set
      • LWW-Set (Add-Wins or Remove-Wins)
      • PN-Counter
      • Lexicographic Counter
        • state = a lexicographic pair for each replica
      • Causal delta-CRDTs
        • DotSet, DotFun, DotMap
        • Enable-Wins Flag
        • Multi-Value Register
        • Add-Wins Set (this can be seen as a map from elements to enable-wins flags, but with a single causal context)
        • Remove-Wins Set
        • Nesting CRDTs in a map