points by MazeChaZer 1 year ago

The observation of this article is spot on! CRDTs are an awesome formal model for distributed data structures, but I was always bothered by the notion that all conflicts must be resolved automatically (hence also the name, conflict-free replicated data type). As the article illustrated, this is a hopeless endeavor. I believe what is needed is a proper structured representation of conflicts, that allows for sharing them and resolving them collaboratively, giving back control to the users and supporting them in the process. One of my favorite papers “Turning Conflicts into Collaboration” [1] makes a compelling argument for this idea.

As part of my ongoing PhD studies, we have developed our own formal model for structured conflict representation, based on lattice theory: “Lazy Merging: From a Potential of Universes to a Universe of Potentials” [2]. Incidentally, it is also a CRDT, but it does not attempt to resolve conflicts automatically. Instead, it represents them within the collaborative documents. Approaching the problem from mathematics allowed us to arrive at a simple conceptual model that can guarantee strong properties, like, e.g., the completeness, minimality, and uniqueness of merges, even after repeated merges of existing conflicts. And merges can be calculates very easily. I always wanted to make a blog post about it, but I never came around to do it.

[1] https://doi.org/10.1007/s10606-012-9172-4

[2] https://doi.org/10.14279/tuj.eceasst.82.1226

crabmusket 1 year ago

Thanks for those citations, they look really interesting!

> hence also the name, conflict-free replicated data type

When I was introduced to CRDTs the acronym stood for commutative replicated data types (eg in the paper by Shapiro et al). I prefer this actually, despite it being harder to pronounce.

A conflict is a complicated idea, and while "conflict free" is a technically correct way of describing the result, it can be misleading as evidenced by this post and your comment.

Commutativity is the property that when Bob applies changes in the order [Bob, Alice] and Alice applies changes in the order [Alice, Bob] that they both end up with the same document. It doesn't imply that the document is somehow "free" of "conflicts" in a sense that may be meaningful at a higher level of abstraction.