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:

  1. Are there any atomic snapshot algorithms concerning the special tree structures of the underlying shared registers? (I found nothing closely related.)
  2. 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.
  • $\begingroup$ Since you asked for a comment on this elsewhere: As you write, every process has a register which only he can write (single-writer,multi-reader). While you could consider them all being children of one (directory) (z)node, why should this change anything? What could change complexity is if the shared memory somehow provides additional semantics. This could be the case for filesystems, but I don't see how it is related to being in a tree... $\endgroup$
    – Martin B.
    Commented Jan 20, 2014 at 14:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.