Blogs (1) >>
POPL 2019
Sun 13 - Sat 19 January 2019 Cascais, Portugal
Wed 16 Jan 2019 10:57 - 11:19 at Sala II - Concurrency Chair(s): Ori Lahav

Verification of concurrent data structures is one of the most challenging tasks in software verification. The topic has received considerable attention over the course of the last decade. Nevertheless, human-driven techniques remain cumbersome and notoriously difficult while automated approaches suffer from limited applicability. The main obstacle for automation is the complexity of concurrent data structures. This is particularly true in the absence of garbage collection. The intricacy of lock-free memory management paired with the complexity of concurrent data structures makes automated verification prohibitive.

In this work we present a method for verifying concurrent data structures and their memory management separately. We suggest two simpler verification tasks that imply the correctness of the data structure. The first task establishes an over-approximation of the reclamation behavior of the memory management. The second task exploits this over-approximation to verify the data structure without the need to consider the implementation of the memory management itself. To make the resulting verification tasks tractable for automated techniques, we establish a second result. We show that a verification tool needs to consider only executions where a single memory location is reused. We implemented our approach and were able to verify linearizability of Michael&Scott’s queue and the DGLM queue for both hazard pointers and epoch-based reclamation. To the best of our knowledge, we are the first to verify such implementations fully automatically.

Wed 16 Jan

POPL-2019-Research-Papers
10:35 - 12:03: Research Papers - Concurrency at Sala II
Chair(s): Ori LahavTel Aviv University
POPL-2019-Research-Papers10:35 - 10:57
Talk
Nikos Gorogiannis, Peter W. O'HearnFacebook and University College London, Ilya SergeyYale-NUS College and National University of Singapore
Link to publication DOI Pre-print Media Attached File Attached
POPL-2019-Research-Papers10:57 - 11:19
Talk
Link to publication DOI Pre-print Media Attached File Attached
POPL-2019-Research-Papers11:19 - 11:41
Talk
Klaus v. GleissenthallUniversity of California at San Diego, USA, Rami Gökhan KıcıUniversity of California at San Diego, USA, Alexander Bakst, Deian StefanUniversity of California San Diego, Ranjit JhalaUniversity of California, San Diego
Link to publication DOI Media Attached
POPL-2019-Research-Papers11:41 - 12:03
Talk
Michael EmmiSRI International, Constantin EneaUniversité Paris Diderot
Link to publication DOI Media Attached File Attached