Order, Lattices and Conflict-Free Replicated Data Types

1. Conflict-Free Replicated Data Types
   1. Instead of shared central state, shared state in distributed replicas
      1. Fast, not blocking local reads
      2. Fast, not blocking local writes - temporary inconsistencies between replicas
      3. Conflict-free replica synchronisation at arbitrary times - eventual consistency
      4. No central state - no single point of failure
      5. Replacement for RPC-like APIs
   2. Advatageous even when single replica
      1. Irrefutable writes - accepting writes as undeniable facts
      2. Append-only writes - data can only "grow"
      3. Transaction-less - consequence of the above
      4. Contradictory writes - possible but explicitly modeled
   3. New ACID
      1. Let a, b, and c be replicas and + be a replicat "merge" operation
      2. Associativity - a + (b + c) == (a + b) + c, handles arbitrary grouping of merges
      3. Commutativity - a + b == b + a - handles out-of-order merges
      4. Idempotence - a + a == a - handles duplicate merges
      5. Distributed - remote replicas merges
2. Maths behind CRDTs
   1. Type - a collection of values
   2. Partial order - values of type can be compared with +> (a kind of "greater or equal")
      1. a +> a - reflexivity
      2. a +> b, b +> a => a == b - antisymmetry
      3. a +> b +> c => a +> c - transitivity
      4. note that there might be that neither a +> b nor b +> a, a and b not comparable, that's why "partial"
   3. Lattice
      1. Algebra (S, \/, /\) where
         1. S is a type
         2. \/ (join) is a binary operator
            1. closed under S - if a and b belongs to S then a \/ b also belongs to S
            2. associative - a \/ (b \/ c) = (a \/ b) \/ c
            3. commutative - a \/ b = b \/ a
            4. idempotent - a \/ a = a
            5. a \/ b +> a
         3. /\ (meet) is a binary operator
            1. closed under S
            2. associative - a /\ (b /\ c) = (a /\ b) /\ c
            3. commutative - a /\ b = b /\ a
            4. idempotent - a /\ a = a
            5. a +> a /\ b
   4. Bounded lattice
      1. Algebra (S, /\, \/, 0, 1)
         1. 0 (bottom) is a value belonging to S
            1. for all a in S, 0 \/ a == a == a \/ 0
         2. 1 (top) is a value belonging to S
            1. for all a in S, 1 /\ a == a == a /\ 1
   5. Finite lattice
      1. Lattice (S, \/, /\) where S is finite
   6. Distributive lattice
      1. a /\ (b \/ c) = (a /\ b) \/ (a \/ c)
   7. Dual 1.
   8. (Bounded) join semilattices examples
      1. GrowingSet is BJS
         1. Set that can only grow in time
         2. S is a set of values of arbitrary type
         3. \/ is sum
         4. 0 is an empty set
      2. ShrinkingSet is JS - set that can only shrink in time
      3. ShrinkingSet is BJS if we know the largest possible set
      4. IncreasingValue is JS - value that can only increase in time
      5. IncreasingValue is BJS if we know minimal possible value
      6. DecreasingValue is JS - value that can only decrease in time
      7. DecreasingValue is BJS if we know maximal possible value
      8. PredAnd a is BJS - functions a -> Bool, Bools anded
      9. PredOr a is BJS - functions a -> Bool, Bools ored
      10. Time-stamped value is JS - pairs (a, Time) (under assumptions about clocks synchronization)
   9. Higher-kinded (bounded) join semilattices
      1. If v is a JS then GrowingMap k s is BJS
         1. GrowingMap is a map where we can only add entries or join existing ones
      2. If e is a JS then GrowingList w is BJS
         1. GrowingList is a list where we can only append values or join existing ones
      3. If a and b are BJSs than (a, b) is BJS
      4. If a and b are BJSs than Either a b is BJS (what are \/ and 0?)
      5. If a is JS than Maybe a is BJS (equivalent to Either () a)
      6. We can combine the above: GrowingMap A (GrowingMap B ((GrowingList (DecreasingValue C), (Either (IncreasingValue D) (GrowingSet E))))) is a BJS as long as
         1. instance Bounded C so that we know maximum value of C
         2. instance Bounded D so that we know minimum value of D
         3. instance Ord E so that we can compare values of Es
   10. Modeling contradictions
       1. Assume a value that we expect to be set at some time and should stay the same since then, what if we get different values?
       2. Same a is a (union) type that can have value Unknown, Unambiguous a or Ambiguous
       3. Same a is BJS as long as we can compare as - instance Eq a
       4. Note we can get the same Unambiguous a multiple times without contradiction (what are \/ and 0?)
   11. Order in join semilattice
       1. If a \/ b == a then we say a +> b, b <+ a, a is greater or equal to b, b is lesser or equal to a
       2. In particular, as a \/ a == a because of idempotence, indeed, a is greater or equal to itself and a is lesser or equal to itself, therefore a is equal to itself.
       3. Intuitively, when a +> b then joining a with b will not introduce anything new than a, a already contains b, a has already contained b
       4. Checking if a +> b is a kind of read operation: it checkes whether b is already contained in a
       5. Example:

       isPersonOlderThan :: Person -> Age -> GrowingMap Person (Increasing Age) -> Bool
       isPersonOlderThan person age personMap = personMap +> singleton person (Increasing age)
       

   12. Mappings between join semilattices
       1. Let's analyse more useful read operation:

       personsAge :: Person -> GrowingMap Person (Increasing Age) -> Maybe (Increasing Age)
       personsAge personMap person = lookup person personMap
       

       1. Notice this is a function from one BJS to another BJS
       2. Left-hand side BJS will only grow, so will the right-hand side BJS
       3. As left-hand side BJS grows, so will the right-hand side BJS - it's a monotonic function
          1. Monotonic mappings between JSs are a category
       4. If f (a \/ b) = f a \/ f b and f 0 = 0 then f it's not only monotonic but homomorphic
          1. Homomorphic mappings between JSs are a category
       5. Propagators concept
   13. References
       1. Introduction to Lattices and Order, 2nd edition, 2012, B. A. Davey, H. A. Priestley
       2. Edward Kmett: Propagators - Boston Haskell
       3. Edward Kmett: Propagators - YOW! Lambda Jam 2016
       4. John Mumm: A CRDT Primer: Defanging Order Theory
       5. Marc Shapiro: Strong Eventual Consistency and Conflict-free Replicated Data Types