Non-volatile memory (NVM) technologies offer DRAM-like speeds with the added benefit of failure resilience. However, developing concurrent programs for NVM can be challenging since programmers must consider both inter-thread synchronisation and durability aspects at the same time. To alleviate this, libraries such as FliT have been developed to manage transformations to durability, allowing a linearizable concurrent object to be converted into a durably linearizable one by replacing the reads/writes to memory by calls to corresponding operations of the FliT library. However, a formal proof of correctness for FliT is missing, and standard proof techniques for durable linearizability are challenging to apply, since FliT itself is not durably linearizable. In this paper, we study the problem of proving correctness of transformations to durability. First, we develop an abstract persistency library (called PLib) that operationally characterises transformations to durability. We prove soundness of PLib via a forward simulation coupled with a prophecy variable used as an oracle about future behaviour. Second, we show correctness of the library FliT by proving that FliTrefines PLib under the realistic PTSO memory model, i.e., the persistent version of TSO memory model implemented by Intel architectures. The proof of refinement between FliT and PLib has been mechanised within the theorem prover KIV. Taken together, these proofs guarantee that FliT is also sound wrt transformations to durability.
Tue 16 JanDisplayed time zone: London change
16:00 - 17:30 | Session 8: Concurrency, Program and System Verification, ClosingVMCAI at Marconi Room Chair(s): Viktor Kunčak EPFL, Switzerland | ||
16:00 20mTalk | Petrification: Software Model Checking for Programs with Dynamic Thread Management VMCAI Matthias Heizmann University of Freiburg, Germany, Dominik Klumpp University of Freiburg, Lars Nitzke University of Freiburg, Frank Schüssele University of Freiburg Pre-print | ||
16:20 20mTalk | A Fully Verified Persistency Library VMCAI Stefan Bodenmüller University of Augsburg, John Derrick , Brijesh Dongol University of Surrey, Gerhard Schellhorn Universitaet Augsburg, Heike Wehrheim University of Oldenburg | ||
16:40 20mTalk | A Navigation Logic for Recursive Programs with Dynamic Thread Creation VMCAI Roman Lakenbrink University of Münster, Markus Müller-Olm University of Münster, Christoph Ohrem University of Münster, Jens Oliver Gutsfeld Westfälische Wilhelm-Universität Münster (WWU), Germany Pre-print | ||
17:00 20mTalk | Borrowable Fractional Ownership Types for Verification VMCAI Takashi Nakayama The University of Tokyo, Yusuke Matsushita The University of Tokyo, Ken Sakayori University of Tokyo, Ryosuke Sato University of Tokyo, Naoki Kobayashi University of Tokyo Pre-print | ||
17:20 10mDay closing | Closing (+ best paper award announcement) VMCAI |