CRDT.Cm

Documentation

class CausalOrd a where

Partial order for causal semantics. Values of some type may be ordered and causally-ordered different ways.

Minimal complete definition

before

Methods

before :: a -> a -> Bool

Instances

CausalOrd (Counter a)

Empty order, allowing arbitrary reordering

Methods

before :: Counter a -> Counter a -> Bool

Eq a => CausalOrd (GSet a)

Methods

before :: GSet a -> GSet a -> Bool

Eq a => CausalOrd (TPSet a)

Methods

before :: TPSet a -> TPSet a -> Bool

CausalOrd (LWW a)

Methods

before :: LWW a -> LWW a -> Bool

class (CausalOrd u, Eq (View u)) => CmRDT u where

Operation-based, or commutative (Cm) replicated data type.

Implementation

In Haskell, a CmRDT implementation consists of 3 types — a payload, an operation (op) and an update.

Payload

Internal state of a replica.

Operation

User's request to update.

Update

Operation to be applied to other replicas.

For many types operation and update may be the same. But for LWW, for instance, this rule doesn't hold: user can request only value, and type attaches a timestamp to it.

Additional constraint — commutativity law

Concurrent updates are observed equally.

∀ up1 up2 s .
concurrent up1 up2 ==>
    observe (updateDownstream up1 . updateDownstream up2 $ s) ==
    observe (updateDownstream up2 . updateDownstream up1 $ s)

Idempotency doesn't need to hold.

Minimal complete definition

updateDownstream

Associated Types

type Op u

type Payload u

type View u

Methods

updateAtSourcePre :: Op u -> Payload u -> Bool

Precondition for updateAtSource. Calculates if the operation is applicable to the current state.

updateAtSource :: Clock m => Op u -> m u

Generate an update to the local and remote replicas. Doesn't have sense if updateAtSourcePre is false.

May or may not use clock.

updateAtSource :: (Clock m, Op u ~ u) => Op u -> m u

Generate an update to the local and remote replicas. Doesn't have sense if updateAtSourcePre is false.

May or may not use clock.

updateDownstream :: u -> Payload u -> Payload u

Apply an update to the payload. An invalid update must be ignored.

view :: Payload u -> View u

Extract user-visible value from payload

view :: Payload u ~ View u => Payload u -> View u

Extract user-visible value from payload

Instances

(Num a, Eq a) => CmRDT (Counter a)

Associated Types

type Op (Counter a) :: *

type Payload (Counter a) :: *

type View (Counter a) :: *

Methods

updateAtSourcePre :: Op (Counter a) -> Payload (Counter a) -> Bool

updateAtSource :: Clock m => Op (Counter a) -> m (Counter a)

updateDownstream :: Counter a -> Payload (Counter a) -> Payload (Counter a)

view :: Payload (Counter a) -> View (Counter a)

Ord a => CmRDT (GSet a)

Associated Types

type Op (GSet a) :: *

type Payload (GSet a) :: *

type View (GSet a) :: *

Methods

updateAtSourcePre :: Op (GSet a) -> Payload (GSet a) -> Bool

updateAtSource :: Clock m => Op (GSet a) -> m (GSet a)

updateDownstream :: GSet a -> Payload (GSet a) -> Payload (GSet a)

view :: Payload (GSet a) -> View (GSet a)

Ord a => CmRDT (TPSet a)

Associated Types

type Op (TPSet a) :: *

type Payload (TPSet a) :: *

type View (TPSet a) :: *

Methods

updateAtSourcePre :: Op (TPSet a) -> Payload (TPSet a) -> Bool

updateAtSource :: Clock m => Op (TPSet a) -> m (TPSet a)

updateDownstream :: TPSet a -> Payload (TPSet a) -> Payload (TPSet a)

view :: Payload (TPSet a) -> View (TPSet a)

Eq a => CmRDT (LWW a)

Associated Types

type Op (LWW a) :: *

type Payload (LWW a) :: *

type View (LWW a) :: *

Methods

updateAtSourcePre :: Op (LWW a) -> Payload (LWW a) -> Bool

updateAtSource :: Clock m => Op (LWW a) -> m (LWW a)

updateDownstream :: LWW a -> Payload (LWW a) -> Payload (LWW a)

view :: Payload (LWW a) -> View (LWW a)

concurrent :: CausalOrd a => a -> a -> Bool

Not comparable, i. e. ¬(a ≤ b) ∧ ¬(b ≤ a).