The availability of Non-Volatile Memory DRAM (known as NVMM) enables the design of recoverable concurrent algorithms. We study the power of software combining in achieving recoverable synchronization and designing persistent data structures. Software combining is a general synchronization approach, which attempts to simulate the ideal world when executing synchronization requests (i.e., requests that must be executed in mutual exclusion). A single thread, called the combiner, executes all active requests, while the rest of the threads are waiting for the combiner to notify them that their requests have been applied. Software combining significantly decreases the synchronization cost and outperforms many other synchronization techniques in various cases.

We identify several parameters, crucial for performance, that an algorithm’s designer has to take into consideration when building highly-efficient persistent synchronization protocols or data structures. For instance, as a recoverable implementation often inherents the synchronization overheads of the concurrent implementation it is inspired from, persistence should not be added on top of heavy software combining protocols (such as OyamaAlg or flat-combining), universal constructions, or transactional memory (TM) systems. Moreover, care should be taken to minimize the persistence overhead not only by reducing the amount of data to be flushed but also the way this flushing is performed.

The paper distills these observations to build recoverable software combining protocols that exhibit much better performance (many times faster) and lower persistence cost, in comparison to a large collection of existing persistent techniques for achieving scalable synchronization. We also built fundamental recoverable data structures, such as stacks and queues, based on these protocols that outperform by far existing recoverable implementations of such data structures.