On: Faster CRDTs (2021)

[kiitos]

CRDT literally means Conflict-free Replicated Data Type. Expecting CRDTs to be conflict-free isn't purism, it's simple validation. Git is, inarguably, not a CRDT.

[LAC-Tech → kiitos]

There are CDTS that have "multiple versions", which look an awful lot like conflicts to me, ie, the Multi-Value Register in this paper:

https://inria.hal.science/inria-00555588/

[kiitos → LAC-Tech]

Multi-value registers are CRDTs for sure. Conflict-free doesn't mean that values can't have concurrent histories (or, as you say, "multiple versions") -- it means that the merge operation always succeeds.

[LAC-Tech → kiitos]

What's the definition of a conflict, then? Equations welcome.

[kiitos → LAC-Tech]

Feel free to read up on CRDTs; I'm confident this will answer your question.

The short answer is, roughly, that a conflict is a discrepancy in state which cannot be mechanically resolved.

[LAC-Tech → kiitos]

I've read a few CRDT papers. Perhaps you could name a specific one.

[yazaddaruvala → kiitos]

> CRDT literally means Conflict-free Replicated Data Type.

Git could be "conflict-free" with a simple `rand(ours, theirs)`.

It would be useless, but technically "conflict-free". Is the addition or removal of that rand function really, pragmatically the difference in the answer to "what is a CRDT?"

[Groxx → yazaddaruvala]

Adding extra rules on top of git to try to turn it into a CRDT doesn't make git one, even if you succeed (and rand would not succeed). You can do that with a pencil and paper, but that doesn't make paper a CRDT.

[kiitos → yazaddaruvala]

This is definitely not true.

Are you open to understanding why this isn't true? If so, I'm happy to help you come to the correct understanding; please ask whatever questions are necessary. Otherwise, then, well, okay!

[jakelazaroff → yazaddaruvala]

`rand` wouldn’t work because all peers must reach the same state without coordination.