Trait garage_table::crdt::Crdt[−][src]

pub trait Crdt {
    fn merge(&mut self, other: &Self);
}
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.

Required methods

Merge the two datastructures according to the CRDT rules. self is modified to contain the merged CRDT value. other is not modified.

Arguments
  • other - the other CRDT we wish to merge with

Implementors