The problem I should have started with is that regular LCAs are not useable for conflict resolution because there can be multiple different LCAs.
For example, in the graph at https://cs.stackexchange.com/questions/72538/lowest-single-c... which LCA do you use to merge 3 and 4?
So you have to use some sort of "unique LCA", which is 0 in the example I gave. But even that does not work as I showed in 2nd example.
0
/\
+1 / \ +2
/ \
1 2
| \ / |
| \/ |
| /\ |
| / \ |
3 3
| \ / |
| \/ |
| /\ |
| / \ |
? ?
Here you've got two choices for LCA (which aren't equivalent but that aside), both will give you the wrong answer. As the correct answer should obviously be 3 as only 1 and 2 were ever added to the counter, exactly once.Basically the problem is that the merge operation isn't idempotent, hence it doesn't define a semilattice, which seems to be what you want if you want to ensure consistency even over distributed systems.
They could have easily fixed this by picking a better merge operation such as a union or maximum, but it's not encouraging when someone picks an illustrative example that doesn't quite work.
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.
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.
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).