Delay-Free Concurrency on Faulty Persistent Memory

Non-volatile memory (NVM) promises persistent main memory that remains correct despite loss of power. This has sparked a line of research into algorithms that can recover from a system crash. Since caches are expected to remain volatile, concurrent data structures and algorithms must be redesigned to guarantee that they are left in a consistent state after a system crash, and that the execution can be continued upon recovery. However, the prospect of redesigning every concurrent data structure or algorithm before it can be used in NVM architectures is daunting. In this paper, we present a construction that takes any concurrent program with reads, writes and CASs to shared memory and makes it persistent, i.e., can be continued after one or more processes fault and have to restart. The converted algorithm has constant computational delay (preserves instruction counts on each process within a constant factor), as well as constant recovery delay (a process can recover from a fault in a constant number of instructions). We show this first for a simple transformation, and then present optimizations to make it more practical, allowing for a trade-off between computation and recovery delay. We also provide an optimized transformation for normalized lock-free data structures, thus speeding up a large class of concurrent algorithms. Finally, we experimentally evaluate these transformations by applying them to a queue. We compare the performance of our transformations to that of a persistent transactional memory framework, Romulus, and to a hand-tuned persistent queue. We show that our optimized transformation performs favorably when compared to Romulus. Furthermore, our optimized transformation is even comparable to the hand-tuned version, showing that the generality we provide comes at very little performance cost.