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.scalaMore details in this paper:http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdfThe logic I'm confused about is on line 139 in Figure 11 on page 6 of ctries-snapshot.pdfThe 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 valueThis 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.
generation-compare-and-swap, or GCAS, in CTries
synchronization