Atomic snapshot memory is a shared memory partitioned into words written (updated) by individual processes, or instantaneously read (scanned) in its entirety.
The Gang of Six algorithm shows that such an atomic snapshot object has wait-free implementation with $\Theta(n^2)$ reads and writes to the component shared registers (when they are restricted to single-writer, $n$-reader registers) in the worst case. This time complexity is then reduced to $\Theta(n \log n)$ using a more clever algorithm.
The two algorithms are both concerned with the most general structure of the underlying single-writer, $n$-reader registers. That is to say, they are simply an unorganized array of registers.
However, in many situations, they are in tree structures, like in a file system. For instance, in ZooKeeper, the in-memory znodes are organized in a hierarchical namespace referred to as the data tree. My questions are:
- Are there any atomic snapshot algorithms concerning the special tree structures of the underlying shared registers? (I found nothing closely related.)
- What are the advantages an atomic snapshot algorithm can take when the underlying shared registers are organized in trees, in hope of reducing the worst-case (or average-case) time complexity.