Atomic snapshots of shared memory

TLDR

Atomic snapshot memory is a shared memory partitioned into words that can be written by individual processes and instantaneously scanned in its entirety, and the constructions presented implement single‑writer snapshot memory from single‑writer, n‑reader registers. The paper presents three wait‑free implementations of atomic snapshot memory. The implementations include an unbounded‑field version that is easy to understand, a bounded‑register version that follows the same correctness ideas, and a multi‑writer version derived from atomic n‑writer, n‑reader registers. All operations require Θ(n²) reads and writes to the component shared registers in the worst case. Authors' abstract provided.

Abstract

This paper introduces a general formulation of atomic snapshot memory , a shared memory partitioned into words written ( updated ) by individual processes, or instantaneously read ( scanned ) in its entirety. This paper presents three wait-free implementations of atomic snapshot memory. The first implementation in this paper uses unbounded (integer) fields in these registers, and is particularly easy to understand. The second implementation uses bounded registers. Its correctness proof follows the ideas of the unbounded implementation. Both constructions implement a single-writer snapshot memory, in which each word may be updated by only one process, from single-writer, n -reader registers. The third algorithm implements a multi-writer snapshot memory from atomic n -writer, n -reader registers, again echoing key ideas from the earlier constructions. All operations require Θ( n 2 ) reads and writes to the component shared registers in the worst case. — Authors' Abstract