Search IconIcon to open search

Order theory

Last updated Jul 8, 2022 Edit Source

From An Abstract Plane: CRDT Primer 1

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

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

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