Search papers, labs, and topics across Lattice.
This paper investigates the feasibility of implementing Read-Modify-Writable (RMWable) snapshots using only read/write operations in asynchronous concurrent shared-memory systems. The authors demonstrate that RMWable snapshots, which allow more complex operations than simple reads and writes on shared memory entries, can be achieved without relying on stronger primitives like compare&swap or load-link/store-conditional. They present two algorithms, one for a standard model with a finite number of processes and another for a model with unbounded concurrency, both using only read/write operations to implement RMWable snapshots.
RMWable snapshots, previously thought to require atomic primitives like compare-and-swap, are now achievable with plain reads and writes.
In the context of asynchronous concurrent shared-memory systems, a snapshot algorithm allows failure-prone processes to concurrently and atomically write on the entries of a shared array MEM , and also atomically read the whole array. Recently, Read-Modify-Writable (RMWable) snapshot was proposed, a variant of snapshot that allows processes to perform operations more complex than just read and write, specifically, each entry MEM[k] is an arbitrary readable object. The known RMWable snapshot algorithms heavily rely on powerful low-level operations such as compare&swap or load-link/store-conditional to correctly produce snapshots of MEM. Following the large body of research devoted to understand the limits of what can be solved using the simple read/write low-level operations, which are known to be strictly weaker than compare&swap and load-link/store-conditional, we explore if RMWable snapshots are possible using only read/write operations. We present two read/write RMWable snapshot algorithms, the first one in the standard concurrent shared-memory model where the number of processes n is finite and known in advance, and the second one in a variant of the standard model with unbounded concurrency, where there are infinitely many processes, but at any moment only finitely many processes participate in an execution.
