Great read. One thing you may be interested to know: when do you need paxos or similar, and when can you get away with gossip and CRDTs? the answer is that the set of domains that can be expressed using CRDTs is exactly the set of monotonic logic.

It’s a bit tricky to explain precisely in an HN comment but basically, something is monotonic if, once you learn that something is true, nothing can disprove it. For example, let’s say you know of a bunch of nodes on a graph, and you’re slowly learning about edges between the nodes. Once you see a cycle, no amount of new edges will ever “disprove” the cycle. So this means that, if what you care about is cycles, then a CRDT is fine. However, let’s say you’re trying to do disturbed garbage collection of nodes that have no edges leading to them. (And as before you’re slowly learning about new edges.) You can see a node has no edges leading to it that you know of, but if you think a node of garbage-collectible you might always be proved wrong by learning about a new edge. So the problem of distributed garbage collection can’t be solved using CRDTs.

There’s a paper on this that you’ll find if you google for the CALM theorem.

This is utterly fantastic stuff. Assuming it's correct, which with Paxos...

That was an interesting read, thanks!