Order theory

From An Abstract Plane: CRDT Primer 1

An order is a binary relation $\le$ on a set $S$, written $<S,\le >$.

• 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\le b$ or $b\le a$
• Partial order: at least one pair a and b in the set, where $a\le b$ or $b\le a$

See also: message ordering, Vector clocks

Joins

An upper bound is an element of the set that is $\ge$ every other element in the set in terms of that relation

When we take the join of $a$ and $b$ (written $a\vee b$), we’re looking for some element $x$ for which $a\le x$ and $b\le x$ where $x$ is the smallest element that satisfies that condition

Join has

1. Commutativity: $a\vee b=b\vee a$
2. Associativity: $(a\vee b)\vee c=a\vee (b\vee c)$
3. Idempotence: $a\vee 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)

Hasse Diagram

We can illustrate the semi-lattice using a Hasse Diagram