8 releases (5 breaking)
|0.5.0||Oct 11, 2023|
|0.4.0||Aug 15, 2023|
|0.3.0||Jul 4, 2023|
|0.2.0||May 31, 2023|
|0.0.0||May 3, 2023|
#531 in Network programming
49 downloads per month
Used in hydroflow
lattices crate provides ergonomic and compsable lattice types. You can also implement custom
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: messages can always arrive out-of-order or duplicated. But if that data is represented as lattices then 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.
Take a look at the
lattices provides implementations of common lattice types:
Max<T>- totally-orderd lattices.
set_union::SetUnion<T>- set-union lattice of scalar values.
map_union::MapUnion<K, Lat>] - scalar keys with nested lattice values.
union_find::UnionFind<K>- union partitions of a set of scalar values.
Vecof nested lattices, like
MapUnion<<usize, Lat>>but without missing entries.
WithBot<Lat>- wraps a lattice in
Noneas the new bottom value.
WithTop<Lat>- wraps a lattice in
Noneas the new top value.
Pair<LatA, LatB>] - product of two nested lattices.
DomPair<LatKey, LatVal>]* - a versioned pair where the
Conflict<T>* - adds a "conflict" top to domain
T. Merging inequal
Ts results in top.
Point<T, *>]* - a single "point lattice" value which cannot be merged with any inequal value.
()- the "unit" lattice, a "point lattice" with unit
()as the only value in the domain.
*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.
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.
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
self was modified (i.e. the value got larger in the
lattice partial order) and
false otherwise (i.e.
other was smaller than
function, which merges two owned values, is provided.
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.
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 the
marker trait to denote when a
PartialOrd implementation is a lattice partial order.
must always agree with the
Additionally, the sealed
NaiveLatticeOrd trait is provided on all lattice types that implement
Clone. This trait provides a
naive_cmp method which derives a lattice order from
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
LatticeFrom is equivalent to the
std::convert::From trait but specific to lattices.
LatticeFrom should be implemented only between different representations of the same lattice
type, e.g. between
set_union::SetUnionHashSet. For compound
lattice (lattices with nested lattice types), the
LatticeFrom implementation should be recursive
for those nested lattices.
A bottom (⊥) is strictly less than all other values. A top (⊤) is strictly greater than all other
IsTop::is_top determine if a lattice instance is top or bottom
For lattice types,
Default::default() must create a bottom value.
should always return true for all lattice types.
Atomize::atomize converts a lattice point into a bunch of smaller lattice points. When these
"atoms" are merged together they will form the original lattice point. See the docs for more