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

precedes

Methods

precedes :: a -> a -> Bool

x precedes y means that x must go before y and y can not go before x.

Instances

Eq a => CausalOrd (TwoPSet a)

Methods

precedes :: TwoPSet a -> TwoPSet a -> Bool

Eq a => CausalOrd (GSet a)

Methods

precedes :: GSet a -> GSet a -> Bool

CausalOrd (Counter a)

Empty order, allowing arbitrary reordering

Methods

precedes :: Counter a -> Counter a -> Bool

CausalOrd (LWW a)

Methods

precedes :: LWW a -> LWW a -> Bool

class (CausalOrd op, Eq (Payload op)) => CmRDT op 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 intent.

Payload

Internal state of a replica.

Intent

User's request to update.

Operation (Op)

Operation to be applied to other replicas.

For many types operation and intent 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.

∀ op1 op2 .
concurrent op1 op2 ==> apply op1 . apply op2 == apply op2 . apply op1

Idempotency doesn't need to hold.

Minimal complete definition

apply

Associated Types

type Intent op

type Payload op

Methods

makeOp :: Clock m => Intent op -> Payload op -> Maybe (m op)

Generate an update to the local and remote replicas.

Returns Nothing if the intended operation is not applicable.

makeOp :: (Intent op ~ op, Applicative m) => Intent op -> Payload op -> Maybe (m op)

Generate an update to the local and remote replicas.

Returns Nothing if the intended operation is not applicable.

apply :: op -> Payload op -> Payload op

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

TODO(Syrovetsky, 2017-12-05) There is no downstream precondition yet. We must make a test for it first.

Instances

Ord a => CmRDT (TwoPSet a)

Associated Types

type Intent (TwoPSet a) :: *

type Payload (TwoPSet a) :: *

Methods

makeOp :: Clock m => Intent (TwoPSet a) -> Payload (TwoPSet a) -> Maybe (m (TwoPSet a))

apply :: TwoPSet a -> Payload (TwoPSet a) -> Payload (TwoPSet a)

Ord a => CmRDT (GSet a)

Associated Types

type Intent (GSet a) :: *

type Payload (GSet a) :: *

Methods

makeOp :: Clock m => Intent (GSet a) -> Payload (GSet a) -> Maybe (m (GSet a))

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

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

Associated Types

type Intent (Counter a) :: *

type Payload (Counter a) :: *

Methods

makeOp :: Clock m => Intent (Counter a) -> Payload (Counter a) -> Maybe (m (Counter a))

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

Eq a => CmRDT (LWW a)

Associated Types

type Intent (LWW a) :: *

type Payload (LWW a) :: *

Methods

makeOp :: Clock m => Intent (LWW a) -> Payload (LWW a) -> Maybe (m (LWW a))

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

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

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