[bkase]

I enjoyed the post, but there's something that bothers me about using the name CRDT.

A CRDT is just what mathematicians (and functional programmers) call a Semilattice[1], right? In general, I find it frustrating when people make up new names for existing mathematical concepts because it deprives others from learning and seeing the big picture. Does this resonate with anyone here?

[rntz]

CRDTs and semilattices are definitely connected, but they're not quite the same thing. A CRDT is a data structure that can be merged across the network in a way that's commutative, associative, and idempotent. That much is exactly the same as a semilattice.

But when people talk about "string CRDTs", the underlying semilattice, the data structure that gets merged, isn't a string; it's usually something rather more complicated. Then there's a _function_ which interprets that more complex data structure as the string that the user or application really cares about.

So a CRDT is a semilattice equipped with an interpretation function.

But it gets even more complicated, because there are many ways to do CRDTs in practice. Rather than gossiping your _entire_ complex data structure across the network ("state-based CRDTs"), usually CRDTs try to only send what's necessary. This leads to optimisations like delta-based and operation-based CRDTs. These optimisations are crucial for real-world use of CRDTs, but their connection to semilattice theory is not immediately clear to me. (That doesn't mean there isn't one, though!)

In any case, the story is a little more complicated than "CRDTS are just a semilattice". I do wish more people knew about the connection, though.