Comment by bos | Hacker News Reader

Comment by bos | Hacker News Reader

This is sort of a revival and elaboration of some of Bram’s ideas from Codeville, an earlier effort that dates back to the early 2000s Cambrian explosion of DVCS.

Codeville also used a weave for storage and merge, a concept that originated with SCCS (and thence into Teamware and BitKeeper).

Codeville predates the introduction of CRDTs by almost a decade, and at least on the face of it the two concepts seem like a natural fit.

It was always kind of difficult to argue that weaves produced unambiguously better merge results (and more limited conflicts) than the more heuristically driven approaches of git, Mercurial, et al, because the edit histories required to produce test cases were difficult (at least for me) to reason about.

I like that Bram hasn’t let go of the problem, and is still trying out new ideas in the space.

In 2007 Bram said to me that my Causal Tree algorithm is a variant of weave. Which is broadly correct. In these 20 years, the family of weave-class algos grew quite big. In my 2020 article, I devoted the intro to making their family portrait https://arxiv.org/abs/2002.09511 Could have been a separate article.

The whole point of using a proper CRDT is that it's easy to reason about what it does. It took me a while to figure out the details of how to build one.

Note that CRDT isn't "a thing". The CRDT paper provides a way to think about and analyze eventually consistent replication mechanisms. So CRDTs weren't "introduced", only the "CRDT way of discussing replication". Every concrete mechanism described in the CRDT paper is very old, widely used for decades beforehand.

This means that everything that implements eventual consistency (including Git) is using "a CRDT".

While this is technically correct, folks discussing CRDTs in the context of text editing are typically thinking of a fairly specific family of algorithms, in which each character (or line) is assigned an immutable ID drawn from some abstract total order. That is the sense in which the original post uses the term (without mentioning a specific total order).

Reply on news.ycombinator.com