Nesting-Safe Recoverable Linearizability: Modular Constructions for Non-Volatile Memory
Nesting-Safe Recoverable Linearizability: Modular Constructions for Non-Volatile Memory
复制标题
嵌套安全的可恢复线性度：非易失性存储器的模块化结构
DOI：
10.1145/3212734.3212753
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Danny Hendler
中科院分区：
文献类型：
--
作者：
H. Attiya;Ohad Ben;Danny Hendler
提出了一种新的抽象的非易失性内存的单进程崩溃恢复模型，该模型支持模块化，使得复杂的可恢复对象可以由简单的可恢复基本对象以模块化的方式构造出来。在这个模型的框架内，我们定义了嵌套安全可恢复线性性（NRL）——一种新的正确性条件，它捕获了嵌套可恢复对象的需求。非正式地，NRL允许恢复代码延长失败操作的间隔，直到恢复代码成功完成（可能在多次失败和恢复尝试之后）。与以前的正确性定义不同，NRL条件意味着，在恢复之后，实现的（更高级别的）可恢复操作能够完成对基本对象操作的调用并获得其响应。我们提出了嵌套安全可恢复原语的算法，即广泛使用的原语共享内存操作（如读、写、测试与设置和比较与交换）的可恢复版本，可用于实现更高级别的可恢复对象。然后，我们举例说明如何使用这些可恢复的基对象来构造可恢复的计数器对象。最后，我们证明了读、写和TAS操作中可恢复的测试和设置（TAS）对象的无等待实现的不可能结果，从而表明我们的模型也有助于严格分析可恢复并发对象的局限性。
We presents a novel abstract individual-process crash-recovery model for non-volatile memory, which enables modularity, so that complex recoverable objects can be constructed in a modular manner from simpler recoverable base objects. Within the framework of this model, we define nesting-safe recoverable linearizability (NRL) -- a novel correctness condition that captures the requirements for nesting recoverable objects. Informally, NRL allows the recovery code to extend the interval of the failed operation until the recovery code succeeds to complete (possibly after multiple failures and recovery attempts). Unlike previous correctness definitions, the NRL condition implies that, following recovery, an implemented (higher-level) recoverable operation is able to complete its invocation of a base-object operation and obtain its response. We present algorithms for nesting-safe recoverable primitives, namely, recoverable versions of widely-used primitive shared-memory operations such as read, write, test-and-set and compare-and-swap, which can be used to implement higher-level recoverable objects. We then exemplify how these recoverable base objects can be used for constructing a recoverable counter object. Finally, we prove an impossibility result on wait-free implementations of recoverable test-and-set (TAS) objects from read, write and TAS operations, thus demonstrating that our model also facilitates rigorous analysis of the limitations of recoverable concurrent objects.