POPL 2024
Sun 14 - Sat 20 January 2024 London, United Kingdom

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 Jan

Displayed 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
20m
Talk
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
20m
Talk
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
20m
Talk
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
20m
Talk
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
10m
Day closing
Closing (+ best paper award announcement)
VMCAI