The Inherent Cost of Remembering Consistently

Non-volatile memory (NVM) promises fast, byte-addressable and durable storage, with raw access latencies in the same order of magnitude as DRAM. But in order to take advantage of the durability of NVM, programmers need to design persistent objects which main- tain consistent state across system crashes and restarts. Concurrent implementations of persistent objects typically make heavy use of expensive persistent fence instructions to order NVM accesses, thus negating some of the performance benefits of NVM. This raises the question of the minimal number of persistent fence instructions required to implement a persistent object. We answer this question in the deterministic lock-free case by providing lower and upper bounds on the required number of fence instructions. We obtain our upper bound by presenting a new universal construction that implements durably any object using at most one persistent fence per update operation invoked. Our lower bound states that in the worst case, each process needs to issue at least one persistent fence per update operation invoked.

Jeremy Fineman
Presented at:
30th ACM Symposium on Parallelism in Algorithms and Architectures, Vienna, Austria, July 16 - 18, 2018

 Record created 2018-05-31, last modified 2019-06-19

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)