The lattices Crate

The lattices crate provides ergonomic and compsable lattice types. Users can also implement their own lattices via a few simple traits.

Lattices are an incredibly powerful mathematical concept which can greatly simplify the trickiness of distributed computing. They align very well with the reality of what happens physically in a distrubted system; even when data messages are reordered or duplicated, if that data is represented as lattices all machines will always reach the same end result simply by merging the data together. One popular way of lattices are currently used in distributed systems is as the data underlying Conflict-free Replicated Data Types (CRDTs).

Lattices also allow us to harness the power of the CALM Theorem: "a program has a consistent, coordination-free distributed implementation if and only if it is monotonic." Lattice state is always monotonic, meaning any part of a distributed system built on lattice state can be freely distributed with no coordination overhead. The goal of the Hydro Project is to allow users to write programs that automatically scale and distribute effortlessly.

For more information on the underlying mathematics of lattices and monotonicity, take a look at Lattice Math section of the Hydroflow Book and Section 2 of the Hydroflow Thesis.

Take a look at the lattice rustdocs.

Lattices

lattices provides implementations of common lattice types:

*Special implementations which do not obey all lattice properties but are still useful under certain circumstances.

Additionally, custom lattices can be made by implementing the traits below.

Traits

A type becomes a lattice by implementing one or more traits starting with Merge. These traits are already implemented for all the provided lattice types.

Merge

The main trait is Merge, which defines a lattice merge function (AKA "join" or "least upper bound"). Implementors must define the Merge::merge method which does a merge in-place into &mut self. The method must return true if self was modified (i.e. the value got larger in the lattice partial order) and false otherwise (i.e. other was smaller than self). The Merge::merge_owned function, which merges two owned values, is provided.

The merge method must be associative, commutative, and idempotent. This is not checked by the compiler, but the implementor can use the test::check_lattice_properties method to spot-check these properties on a collection of values.

PartialOrd, LatticeOrd, and NaiveLatticeOrd

Rust already has a trait for partial orders, PartialOrd, which should be implemented on lattice types. However that trait is not specific to lattice partial orders, therefore we provide theLatticeOrd<Rhs>: PartialOrd<Rhs> marker trait to denote when a PartialOrd implementation is a lattice partial order. LatticeOrd must always agree with the Merge function.

Additionally, the sealed NaiveLatticeOrd trait is provided on all lattice types that implement Merge and Clone. This trait provides a naive_cmp method which derives a lattice order from the Merge function directly. However the implementation is generally slow and inefficient.

Implementors should use the test::check_partial_ord_properties method to check their PartialOrd implementation, and should use the test::check_lattice_ord to ensure the partial order agrees with the Merge-derived NaiveLatticeOrd order.

ConvertFrom

ConvertFrom is equivalent to the std::convert::From trait but with some extra lattice-specific semantics. ConvertFrom should be implemented only between different representations of the same lattice type, e.g. between set_union::SetUnionBTreeSet and set_union::SetUnionHashSet. For compound lattice (lattices with nested lattice types), the ConvertFrom implementation should be recursive for those nested lattices.

Next

Take a look at Lattice Math for a simple explanation and summary of what lattices are exactly. See the lattice rustdocs here.