Trait garage_table::crdt::Crdt [−][src]
Expand description
Definition of a CRDT - all CRDT Rust types implement this.
A CRDT is defined as a merge operator that respects a certain set of axioms.
In particular, the merge operator must be commutative, associative,
idempotent, and monotonic.
In other words, if a
, b
and c
are CRDTs, and ⊔
denotes the merge operator,
the following axioms must apply:
a ⊔ b = b ⊔ a (commutativity)
(a ⊔ b) ⊔ c = a ⊔ (b ⊔ c) (associativity)
(a ⊔ b) ⊔ b = a ⊔ b (idempotence)
Moreover, the relationship ≥
defined by a ≥ b ⇔ ∃c. a = b ⊔ c
must be a partial order.
This implies a few properties such as: if a ⊔ b ≠ a
, then there is no c
such that (a ⊔ b) ⊔ c = a
,
as this would imply a cycle in the partial order.