4 ms·

The most surprising part of this article for someone uninitiated like myself is probably that products/algorithms are claiming this automatic reconciliation is

The most surprising part of this article for someone uninitiated like myself is probably that products/algorithms are claiming this automatic reconciliation is consistently possible. Maybe I've spent too much time resolving code merge conflicts by hand, but this seems intuitively obvious to me... Feels like https://xkcd.com/1831 https://xkcd.com/1831

williamstein 2y ago
What they claim is that if all editing stops, then after a period of time everybody will be looking at the SAME document. This is what is meant by "eventual consistency". Achieving this in general is indeed a difficult problem, but (some of) these algorithms do solve it, though it can be tricky to correctly prove that they do. I agree that it is not possible to ensure that the document everybody is looking at is what they actually wanted it to be. However, there are some options for what happens, where some results may be technically correct -- we are all looking at the same thing -- but obviously really bad. This beautiful talk has some examples: https://www.youtube.com/watch?v=x7drE24geUw https://www.youtube.com/watch?v=x7drE24geUw
- robertclaus 2y ago
  Isn't eventual consistency theoretically trivial...? You just delete the whole document after every transaction. I think it's safe to assume anyone talking about this _means_ the results remain meaningful - which for text/meaning is subjective.
  - williamstein 2y ago
    Proving that there exists an algorithm that results in an eventually consistent view of the document is trivial. However, that's not what we're talking about. Instead, researchers define a specific algorithm (e.g., involving CRDT's or OT's or something else), then prove that their algorithm results in an eventually consistent state. This reminds me a little of the relationship between proving that there exists an algorithm to factor all positive integers (this is trivial) and proving there exists a subexponential time algorithm to factor integers, which is much less trivial (see https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factori...).

williamstein 2y ago

What they claim is that if all editing stops, then after a period of time everybody will be looking at the SAME document. This is what is meant by "eventual consistency". Achieving this in general is indeed a difficult problem, but (some of) these algorithms do solve it, though it can be tricky to correctly prove that they do. I agree that it is not possible to ensure that the document everybody is looking at is what they actually wanted it to be. However, there are some options for what happens, where some results may be technically correct -- we are all looking at the same thing -- but obviously really bad. This beautiful talk has some examples: https://www.youtube.com/watch?v=x7drE24geUw https://www.youtube.com/watch?v=x7drE24geUw

robertclaus 2y ago
Isn't eventual consistency theoretically trivial...? You just delete the whole document after every transaction. I think it's safe to assume anyone talking about this _means_ the results remain meaningful - which for text/meaning is subjective.
- williamstein 2y ago
  Proving that there exists an algorithm that results in an eventually consistent view of the document is trivial. However, that's not what we're talking about. Instead, researchers define a specific algorithm (e.g., involving CRDT's or OT's or something else), then prove that their algorithm results in an eventually consistent state. This reminds me a little of the relationship between proving that there exists an algorithm to factor all positive integers (this is trivial) and proving there exists a subexponential time algorithm to factor integers, which is much less trivial (see https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factori...).