MemSnap: Checkpointing Modern Shared-Memory (Abstract)
Prasad Jayanti, Siddhartha Jayanti, Sucharita Jayanti · 2025
Modern multiprocessors support read-modify-write (RMW) primitives, such as compare-and-swap, fetch-and-add, and fetch-and-store, in addition to standard reads and writes. Thus, checkpointing the shared-memory of a modern multicore requires a variant of the snapshot object, which allows components to be updated via all the RMW operations supported by hardware. We design such an RMWable, checkpoint snapshot object called MemSnap [9]. MemSnap is adaptive, meaning that it supports a click operation which quickly takes an implicit snapshot (returning nothing), and an observe operation for processes to read the values of the components in the latest snapshot. The algorithm is linearizable, wait-free, and time and space optimal: it requires only O(1) time per read, write, or RMW update; O(1) time per click; O(1) time per observe; and uses only O(1) space per component. In addition, MemSnap supports a dynamic set of components---meaning that components can be created and deleted in the course of an execution---and it supports dynamic access---meaning an arbitrary number of processes of arbitrary names can access the object. The MemSnap algorithm is concise, efficient, and elegant; however, its behavior is tantalizingly complex, since it exhibits far-future linearization. We prove its correctness via the meta-configuration tracking technique [10].