Safe Haskell | None |
---|---|
Language | Haskell2010 |
Documentation
class CausalOrd a where Source #
Partial order for causal semantics. Values of some type may be ordered and causally-ordered different ways.
class (CausalOrd op, Eq (Payload op)) => CmRDT op where Source #
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.
makeOp :: Clock m => Intent op -> Payload op -> Maybe (m op) Source #
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) Source #
Generate an update to the local and remote replicas.
Returns Nothing
if the intended operation is not applicable.
apply :: op -> Payload op -> Payload op Source #
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.
concurrent :: CausalOrd a => a -> a -> Bool Source #
Not comparable, i. e. ¬(a ≤ b) ∧ ¬(b ≤ a).