Order theory
From An Abstract Plane: CRDT Primer 1
An order is a binary relation $\leq$ on a set $S$, written $<S,\leq>$.
- If two things $a$ and $b$ are incomparable, we write it $a \parallel b$
- Total order: for all a and b in the set, either $a \leq b$ or $b \leq a$
- Partial order: at least one pair a and b in the set, where $a \leq b$ or $b \leq a$
See also: message ordering, Vector clocks
# Joins
An upper bound is an element of the set that is $\geq$ every other element in the set in terms of that relation
When we take the join of $a$ and $b$ (written $a \lor b$), we’re looking for some element $x$ for which $a \leq x$ and $b \leq x$ where $x$ is the smallest element that satisfies that condition
Join has
- Commutativity: $a \lor b = b \lor a$
- Associativity: $(a \lor b) \lor c = a \lor (b \lor c)$
- Idempotence: $a \lor a = a$
When it comes to CRDTs, what we’re looking for is the ability to apply an operation in any order and as many times as we want without corrupting the result. The laws obeyed by joins give us exactly this.
A join semi-lattice then essentially does a topological sort or causal ordering of its elements except all of the elements can be joined (i.e. have a single shared ancestor)
We can illustrate the semi-lattice using a Hasse Diagram
