The data structure is used for example in Scala: https://github.com/scala/scala/blob/v2.12.0-M3/src/library/scala/collection/concurrent/TrieMap.scala
More details in this paper: http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf
The logic I'm confused about is on line 139 in Figure 11 on page 6 of
The code checks if the generation of the root node is the same as the current node before proceeding. To quote the paper,
The idea is to communicate the intent of replacing the value in the I-node and check the generation field in the root before committing to the new value
This is the last sentence of the second paragraph in section 4.1 on page 6. The root generation is changed for example when a snapshot is taken (Figure 7 on page 15).
The question is, I don't see any synchronization mechanism that would prevent updates to the root right after the generation check. To use the papers own words, how is "the intent of replacing the value in the I-node" communicated to other threads attempting to update the root node through snapshots? From what I can tell, the root and the I-node in question can be two distinct nodes, and I'm not sure how the CAS's surrounding the generation check can prevent a race.