The path to durable linearizability
File(s) 3571219.pdf (390.07 KB)
Published version
Author(s)
D'Osualdo, Emanuele
Raad, Azalea
Vafeiadis, Viktor
Type
Journal Article
Abstract
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 of durable 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.
Date Issued
2023-01-01
Date Acceptance
2022-11-07
Citation
Proceedings of the ACM on Programming Languages, 2023, 7 (POPL), pp.748-774
ISSN
2475-1421
Publisher
Association for Computing Machinery (ACM)
Start Page
748
End Page
774
Journal / Book Title
Proceedings of the ACM on Programming Languages
Volume
7
Issue
POPL
Copyright Statement
© 2023 Copyright held by the owner/author(s). This work is licensed under a Creative Commons Attribution 4.0 International License.
License URL
Identifier
10.1145/3571219
Subjects
Persistency
Non-Volatile Memory
Px86
Weak Memory Models
Concurrency
Linearizability
Publication Status
Published
Article Number
26
Date Publish Online
2023-01-11
