we needed to get LCA when merging two histories of data changes, with a very large no of histories and nodes in each history; with branching and merging happening - so to find LCA for 2 histories starting from 2 points we must search backwards across any no of histories, not just walk back along the two given histories.
The published ways for finding LCA seem to assume a pre-scan of all the nodes as the 1st phase, and we wanted to avoid that.
Looked at using a vector clock with each node in history - then we wouldn't need to do any search at all, just knowing the VC's of two starting nodes would give us the VC of the LCA. But had problems with VCs, as we have a large and dynamic no of histories and nodes.
Instead of VC we used a simple scalar counter (similar to the logical clock, used elsewhere) and we do need to do partial search but complexity is expected to be lower. The code seems to work ok. I wonder if anyone else have done something similar or can see some problems.