CRDTs #2: Turtles All the Way Down

Summary

After a lecture on cosmology, William James was challenged by a skeptic: "Your theories are incorrect. The Earth rests on a turtle," "And what holds up the turtle?" James asked. "Another turtle," came the reply. "And what holds that up?" pressed James. The skeptic was undeterred: "You can't fool me, sir. It’s turtles all the way down." — Anecdote attributed to William James ([via J.R. Ross, 1967](https://en.wikipedia.org/wiki/Turtles_all_the_way_down)) This is the 2nd post in a series of 4 posts I'm doing on CRDTs. Please see the intro post for context. Modern distributed systems often seem to rest on an stack of turtles. For every guarantee we make, we seem to rely on a lower-layer assumption. Eventually we're left wondering: what is at the bottom? CRDTs — Conflict-Free Replicated Data Types — are often advertised as a foundation we can finally trust. They promise convergence of state across machines without requiring perfect clocks, global operation ordering, or causal message delivery ... and they do it with math. But many CRDTs sneak in assumptions that don't belong. That's not solid ground. It's not math. It's turtles. In this post, we’ll show how to design CRDT internals properly: ✅ Always in terms of a semilattice structure. ✅ Always with clean algebraic reasoning, without hidden dependencies. ✅ With explicit causality lattices included whenever needed. This will ensure we're always using careful reasoning. Correct CRDTs are semilattices at bottom. And that's math you can count on. 🐢 A Principle for CRDTs: Semilattices All the Way Down Every well-designed CRDT is a semilattice. ✅ A semilattice defines how information grows and merges. ✅ It provides convergence by construction, through clean algebra. In case you've read about a split between so-called "state-based" vs "op-based" CRDTs, you can ignore that for now; it's a turtlish distraction I will fill in below. Here’s what actually matters: A semilattice is: A set of states SSS A join function ⊔:S×S→S\sqcup ...