The Path to Durable Linearizability
The Path to Durable Linearizability
复制标题
持久线性化之路
DOI：
10.1145/3571219
复制
发表时间：
2023
影响因子：
--
通讯作者：
D'Osualdo E
中科院分区：
文献类型：
--
作者：
D'Osualdo E
有越来越多的文献提出了新的和有效的并发数据结构的持久版本，确保一致的状态可以在电源故障或崩溃后恢复。 它们的正确性通常用持久线性化（DL）来表示，这要求各个库操作以与实时顺序一致的顺序原子地执行，此外，从崩溃中恢复返回对应于该序列前缀的状态。 然而，可悲的是，几乎没有任何正式的DL证明，而那些确实存在的证明涵盖了特定（简化）持久化模型上相当简单的持久化算法的正确性。 作为回应，我们提出了一个通用的，功能强大的，模块化的，增量证明技术，可用于指导开发和建立DL。 我们的技术是（1）通用的，因为它不依赖于特定的持久化和/或一致性模型，（2）强大的，因为它可以处理文献中最先进的持久化算法，（3）模块化，因为它允许重用现有的线性化参数，以及（4）增量，因为建立DL的附加要求取决于要验证的算法的复杂性。 我们说明了这种技术的各种版本的持久集，导致Zuriel等人的无链接集。
There is an increasing body of literature proposing new and efficient persistent versions of concurrent data structures ensuring that a consistent state can be recovered after a power failure or a crash. Their correctness is typically stated in terms ofdurable linearizability(DL), which requires that individual library operations appear to be executed atomically in a sequence consistent with the real-time order and, moreover, that recovering from a crash return a state corresponding to a prefix of that sequence. Sadly, however, there are hardly any formal DL proofs, and those that do exist cover the correctness of rather simple persistent algorithms on specific (simplified) persistency models. In response, we propose a general, powerful, modular, and incremental proof technique that can be used to guide the development and establish DL. Our technique is (1)general, in that it is not tied to a specific persistency and/or consistency model, (2)powerful, in that it can handle the most advanced persistent algorithms in the literature, (3)modular, in that it allows the reuse of an existing linearizability argument, and (4)incremental, in that the additional requirements for establishing DL depend on the complexity of the algorithm to be verified. We illustrate this technique on various versions of a persistent set, leading to the link-free set of Zuriel et al.
登录
查看更多内容
影响因子：
1.8
作者：
Raad, Azalea;Doko, Marko;Vafeiadis, Viktor
通讯作者：
Vafeiadis, Viktor
验证持久并发数据结构的正确性：一种健全且完整的方法
影响因子：
1
作者：
Derrick J
通讯作者：
Derrick J
FliT：一个简单高效的持久算法库
DOI：
10.1145/3503221.3508436
发表时间：
2022
期刊：
Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
影响因子：
--
作者：
Wei, Yuanhao;Ben-David, Naama;Friedman, Michal;Blelloch, Guy E.;Petrank, Erez
通讯作者：
Petrank, Erez
影响因子：
0.5
作者：
Schellhorn, Gerhard;Derrick, John;Wehrheim, Heike
通讯作者：
Wehrheim, Heike
C/C 并发的库抽象
DOI：
10.1145/2429069.2429099
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Batty M
通讯作者：
Batty M