Brief Announcement: Using Detectability to Simplify the Design of Concurrent Algorithms for Persistent Memory

The emergence of persistent shared memory in recent years has created new opportunities to rethink classic algorithmic problems in the presence of crash-restart failures, and also new challenges as algorithm designers must account for both failures and concurrency. Recent research has explored algorithm design techniques based on powerful base objects that provide special features to simplify recovery from failures as an alternative to the traditional approach of programming more directly using processor instructions. Notably, Friedman, Herlihy, Marathe, and Petrank introduced detectable objects, which allow an application to resolve the outcome of operations that may have been interrupted by a crash. We propose a transformation that replaces low-level memory operations in a conventional algorithm with operations on detectable base objects that leverage persistent memory to enable recovery from crash-restart failures. The transformation is almost universal, and can be used to obtain efficient solutions to complex and previously unsolved problems.