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.

Conference Day
Wed 16 Jan

Displayed time zone: Belfast change

10:35 - 12:03
ConcurrencyResearch Papers at Sala II
Chair(s): Ori LahavTel Aviv University
10:35
22m
Talk
A True Positives Theorem for a Static Race Detector
Research Papers
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
10:57
22m
Talk
Decoupling Lock-Free Data Structures from Memory Reclamation for Static Analysis
Research Papers
Link to publication DOI Pre-print Media Attached File Attached
11:19
22m
Talk
Pretend Synchrony: Synchronous Verification of Asynchronous Distributed Programs
Research Papers
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
11:41
22m
Talk
Weak-Consistency Specification via Visibility Relaxation
Research Papers
Michael EmmiSRI International, Constantin EneaUniversité Paris Diderot
Link to publication DOI Media Attached File Attached