15 ms·

You do recursive LCA merge, like git. I give a hand-wavy argument on why the algorithm is semantically correct here: https://infinity0.github.io/msg-notes/causa

You do recursive LCA merge, like git. I give a hand-wavy argument on why the algorithm is semantically correct here: https://infinity0.github.io/msg-notes/causal/04-state.html#way-merge https://infinity0.github.io/msg-notes/causal/04-state.html#w...

contravariant 7y ago
Okay, I can see the recursive algorithm working provided the merge works correctly if you've got just 1 LCA. I'm not entirely convinced that the merge for the 'counter' always works if you've got a single LCA though. It seems like it should obviously work, but I'm a bit concerned given that you can easily create a counter example where the formula doesn't work if you allow for multiple LCA. So somehow having a single LCA is vital for the formula to work and it's not entirely obvious to me why. Anyway if you end up just calculating something equivalent to the union of the history (+some interpretation) then you're probably fine.
- infinity0 7y ago
  The recursive algorithm works for any number of LCAs, as I argued. If you're referring to having multiple roots, there are two solutions: (a) define your 3-way-merge primitive (the non-recursive version) to support merging two states against an imaginary "zero" that acts as the single root. So in the counter version you can imagine that everything "actually" starts from 0. (b) arrange your application so there are never multiple roots. In some cases this not really a constraint, usually one single person starts a document and it doesn't make sense to merge something else in later. In some other cases (group chats, tree histories like git) this is probably not acceptable and you will need (a). But in the examples I just gave, a reasonable (a) is fairly straightforward to think of.
  - contravariant 7y ago
    If it works for 1 your algorithm works for any number so far I can follow. It's a bit tricky to show that the 3-way merge always works fine if you've got a single least common ancestor. But yeah it looks like you're fine because any update that both have in common will also have reached the LCA (this was the insight I was missing that explains why a single LCA works and multiple LCA do not if you naively apply the 3-way-merge).

contravariant 7y ago

Okay, I can see the recursive algorithm working provided the merge works correctly if you've got just 1 LCA. I'm not entirely convinced that the merge for the 'counter' always works if you've got a single LCA though. It seems like it should obviously work, but I'm a bit concerned given that you can easily create a counter example where the formula doesn't work if you allow for multiple LCA. So somehow having a single LCA is vital for the formula to work and it's not entirely obvious to me why. Anyway if you end up just calculating something equivalent to the union of the history (+some interpretation) then you're probably fine.

infinity0 7y ago
The recursive algorithm works for any number of LCAs, as I argued. If you're referring to having multiple roots, there are two solutions: (a) define your 3-way-merge primitive (the non-recursive version) to support merging two states against an imaginary "zero" that acts as the single root. So in the counter version you can imagine that everything "actually" starts from 0. (b) arrange your application so there are never multiple roots. In some cases this not really a constraint, usually one single person starts a document and it doesn't make sense to merge something else in later. In some other cases (group chats, tree histories like git) this is probably not acceptable and you will need (a). But in the examples I just gave, a reasonable (a) is fairly straightforward to think of.
- contravariant 7y ago
  If it works for 1 your algorithm works for any number so far I can follow. It's a bit tricky to show that the 3-way merge always works fine if you've got a single least common ancestor. But yeah it looks like you're fine because any update that both have in common will also have reached the LCA (this was the insight I was missing that explains why a single LCA works and multiple LCA do not if you naively apply the 3-way-merge).