Technical Report CS759

The snapshot object is an important tool for constructing wait-free asynchronous algorithms. We relate the snapshot object to the lattice agreement decision problem. It is shown that any algorithm for solving lattice agreement can be transformed into an implementation of a snapshot object. The overhead cost of this transformation is only a linear number of operations on atomic single-writer multi-reader registers. The transformation uses an unbounded amount of shared memory. Four lattice agreement algorithms are presented:

• A deterministic algorithm that uses O(\log^2 n) operations on (dynamic) 2-processor Test{\cal \&}Set registers, plus O(n) operations on (dynamic) atomic single-writer multi-reader registers.
• A deterministic algorithm that uses O(n \log^2 n) operations on (static) 2-processor Test{\cal \&}Set registers, plus O(n \log^2 n) operations on (static) atomic single-writer multi-reader registers.
• A randomized algorithm that uses an expected number of O(n) operations on (dynamic) atomic single-writer multi-reader registers.
• A randomized algorithm that uses and expected number of O(n \log^2 n) operations on (static) atomic single-writer multi-reader registers.