mdcs_core/
lattice.rs

1//! Join-semilattice trait - the mathematical foundation of CRDTs
2//!
3//! A join-semilattice (S, ⊔) satisfies:
4//!  - Commutativity: a ⊔ b = b ⊔ a
5//! - Associativity: (a ⊔ b) ⊔ c = a ⊔ (b ⊔ c)
6//! - Idempotence:  a ⊔ a = a
7//!
8//!  These properties guarantee convergence regardless of message order.
9
10use std::cmp::Ordering;
11
12/// The core CRDT trait.  All state-based CRDTs implement this.
13pub trait Lattice: Clone + PartialEq {
14    /// The bottom element (identity for join)
15    fn bottom() -> Self;
16
17    /// Join operation (least upper bound)
18    /// Must be commutative, associative, and idempotent
19    fn join(&self, other: &Self) -> Self;
20
21    /// Partial order derived from join:  a ≤ b iff a ⊔ b = b
22    fn partial_cmp_lattice(&self, other: &Self) -> Option<Ordering> {
23        let joined = self.join(other);
24        if &joined == self && &joined == other {
25            Some(Ordering::Equal)
26        } else if &joined == other {
27            Some(Ordering::Less)
28        } else if &joined == self {
29            Some(Ordering::Greater)
30        } else {
31            None // Concurrent/incomparable
32        }
33    }
34
35    /// Check if self ≤ other in the lattice order
36    fn leq(&self, other: &Self) -> bool {
37        matches!(
38            self.partial_cmp_lattice(other),
39            Some(Ordering::Less) | Some(Ordering::Equal)
40        )
41    }
42
43    /// Join-assign:  self = self ⊔ other
44    fn join_assign(&mut self, other: &Self) {
45        *self = self.join(other);
46    }
47}
48
49/// Marker trait for CRDTs that support delta operations
50pub trait DeltaCRDT: Lattice {
51    /// The delta state type (often the same as Self)
52    type Delta: Lattice;
53
54    /// Split off pending deltas, returning them and resetting internal delta buffer
55    fn split_delta(&mut self) -> Option<Self::Delta>;
56
57    /// Apply a delta to the state
58    fn apply_delta(&mut self, delta: &Self::Delta);
59}
mdcs_core/lattice.rs

mdcs_core/
lattice.rs
