Towards a practical snapshot algorithm

An atomic snapshot memory is an implementation of a multiple-location shared memory that can be atomically read in its entirety without preventing concurrent writing. The design of wait-free implementations of atomic snapshot memories has been the subject of extensive theoretical research in recent years. This paper introduces the coordinated-collect algorithm, a novel wait-free atomic snapshot construction which we believe is a first step in taking snapshots from theory to practice. Unlike previous algorithms, it uses currently available multiprocessor synchronization operations to provide an algorithm that has only O(1) update complexity and O(n) scan complexity, with very small constants. We evaluated the performance of known snapshot algorithms for a collection of benchmarks on a simulated distributed shared-memory multiprocessor. Our empirical evidence suggests that coordinated-collect will outperform all known wait-free, lock-free, and locking snapshot algorithms in terms of overall throughput and latency.

Authors

• Yaron Riany
• Nir Shavit
• Dan Touitou

Keywords

• Shared memory multiprocessors
• Wait-free synchronization
• Memory snapshots
• Atomic operations
• Compare and swap