Automatically proving linearizability of concurrent data structures remains a key challenge for verification. We present temporal interpolation as a new proof principle to guide automated proof search using hindsight arguments within concurrent separation logic. Temporal interpolation offers an easy-to-automate alternative to prophecy variables and has the advantage of structuring proofs into easy-to-discharge hypotheses. Additionally, we advance hindsight theory by integrating it into a program logic, bringing formal rigor and complementary proof machinery. We substantiate the usefulness of temporal interpolation by implementing it in a tool and using it to automatically verify the Logical Ordering tree. The proof is challenging due to future-dependent linearization points and complex structure overlays. It is the first formal proof of this data structure. Interestingly, our formalization revealed an unknown bug and an existing informal proof as erroneous.
Wed 21 JunDisplayed time zone: Eastern Time (US & Canada) change
09:00 - 11:00 | PLDI: Memory Models & Program LogicsPLDI Research Papers at Cypress 1 Chair(s): Matthew J. Parkinson Azure Research, Microsoft, UK | ||
09:00 20mTalk | Compound Memory Models PLDI Research Papers Andrés Goens the University of Edinburgh, Soham Chakraborty TU Delft, Susmit Sarkar University of St. Andrews, Sukarn Agarwal University of Edinburgh, Nicolai Oswald NVIDIA, Vijay Nagarajan University of Edinburgh, UK DOI | ||
09:20 20mTalk | Putting Weak Memory in Order via a Promising Intermediate Representation PLDI Research Papers Sung-Hwan Lee Seoul National University, Minki Cho Seoul National University, Roy Margalit Tel Aviv University, Israel, Chung-Kil Hur Seoul National University, Ori Lahav Tel Aviv University DOI | ||
09:40 20mTalk | Optimal Reads-From Consistency Checking for C11-Style Memory Models PLDI Research Papers Hünkar Can Tunç Aarhus University, Parosh Aziz Abdulla Uppsala University, Sweden, Soham Chakraborty TU Delft, Shankaranarayanan Krishna IIT Bombay, India, Umang Mathur National University of Singapore, Andreas Pavlogiannis Aarhus University DOI Pre-print | ||
10:00 20mTalk | VMSL: A Separation Logic for Mechanised Robust Safety of Virtual Machines Communicating above FF-A PLDI Research Papers Zongyuan Liu Aarhus University, Sergei Stepanenko Aarhus University, Jean Pichon-Pharabod Aarhus University, Amin Timany Aarhus University, Aslan Askarov Aarhus University, Lars Birkedal Aarhus University DOI | ||
10:20 20mTalk | Embedding Hindsight Reasoning in Separation Logic PLDI Research Papers DOI | ||
10:40 20mTalk | Beyond Backtracking: Connections in Fine-Grained Concurrent Separation Logic PLDI Research Papers Ike Mulder Radboud University Nijmegen, Lukasz Czajka Heliax AG, Robbert Krebbers Radboud University Nijmegen DOI Pre-print | ||
