Wed 15 Jun 2022 16:30 - 16:50 at Cockatoo - Concurrency Chair(s): Umang Mathur

Visibility relations have been proposed by Henzinger et al. as an abstraction for proving linearizability of concurrent algorithms that obtains modular and reusable proofs. This is in contrast to the customary approach based on exhibiting the algorithm’s linearization points. In this paper we apply visibility relations to develop modular proofs for three elegant concurrent snapshot algorithms of Jayanti. The proofs are divided into components of increasing level of abstraction, using type-theoretic notions of signatures and functors (i.e., dependent $\Sigma$ and $\Pi$ types) as interfaces. The proofs are modular because the components at higher abstraction levels are shared, i.e., they apply to all three algorithms simultaneously. Importantly, the interface properties mathematically capture Jayanti’s original intuitions that have previously been given only informally.

Wed 15 Jun

Displayed time zone: Pacific Time (US & Canada) change

15:30 - 16:50
ConcurrencySIGPLAN Track at Cockatoo
Chair(s): Umang Mathur National University of Singapore
15:30
20m
Talk
(PLDI 2020) Inductive Sequentialization of Asynchronous Programs
SIGPLAN Track
Constantin Enea Ecole Polytechnique / LIX / CNRS, Thomas A. Henzinger IST Austria, Austria, Bernhard Kragl IST Austria, Suha Orhun Mutluergil IRIF, France / University Paris Diderot, France / CNRS, France, Shaz Qadeer Novi, USA
15:50
20m
Talk
(PLDI 2021) When Threads Meet Events: Efficient and Precise Static Race Detection with Origins
SIGPLAN Track
Bozhen Liu Texas A&M University, USA, Peiming Liu Texas A&M University, Yanze Li University of British Columbia, Chia-Che Tsai Texas A&M University, Dilma Da Silva Texas A&M, Jeff Huang Texas A&M University
16:10
20m
Talk
(POPL 2021) Optimal Prediction of Synchronization-Preserving Races
SIGPLAN Track
Umang Mathur National University of Singapore, Andreas Pavlogiannis Aarhus University, Mahesh Viswanathan University of Illinois at Urbana-Champaign
16:30
20m
Talk
(POPL 2022) Visibility Reasoning for Concurrent Snapshot Algorithms
SIGPLAN Track
Joakim Öhman IMDEA Software Institute; Universidad Politécnica de Madrid, Aleksandar Nanevski IMDEA Software Institute