Write a Blog >>
PLDI 2020
Mon 15 - Fri 19 June 2020
Wed 17 Jun 2020 11:40 - 12:00 at PLDI Research Papers live stream - Verification I Chair(s): Stephen N. Freund

Asynchronous programs are notoriously difficult to reason about because they spawn computation tasks which take effect asynchronously in a nondeterministic way. Devising inductive invariants for such programs requires understanding and stating complex relationships between an unbounded number of computation tasks in arbitrarily long executions. In this paper, we introduce \emph{inductive sequentialization}, a new proof rule that sidesteps this complexity via a \emph{sequential reduction}, a sequential program that captures every behavior of the original program up to reordering of coarse-grained commutative actions. A sequential reduction of a concurrent program is easy to reason about since it corresponds to a simple execution of the program in an idealized synchronous environment, where processes act in a fixed order and at the same speed. We have implemented and integrated our proof rule in the CIVL verifier, allowing us to provably derive fine-grained implementations of asynchronous programs. We have successfully applied our proof rule to a diverse set of message-passing protocols, including leader election protocols, two-phase commit, and Paxos.

Wed 17 Jun

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

10:40 - 12:00
10:40
20m
Talk
Verifying Concurrent Search Structure Templates
PLDI Research Papers
Siddharth Krishna Microsoft Research, Cambridge, Nisarg Patel New York University, USA, Dennis Shasha New York University, USA, Thomas Wies New York University, USA
11:00
20m
Talk
Armada: Low-Effort Verification of High-Performance Concurrent Programs
PLDI Research Papers
Jacob R. Lorch Microsoft Research, USA, Yixuan Chen University of Michigan, USA / Yale University, USA, Manos Kapritsos University of Michigan, USA, Bryan Parno Carnegie Mellon University, USA, Shaz Qadeer Novi, USA, Upamanyu Sharma University of Michigan, USA, James R. Wilcox Certora, USA, Xueyuan Zhao Carnegie Mellon University, USA
DOI
11:20
20m
Talk
Decidable Verification under a Causally Consistent Shared Memory
PLDI Research Papers
Ori Lahav Tel Aviv University, Israel, Udi Boker IDC Herzliya, Israel
11:40
20m
Talk
Inductive Sequentialization of Asynchronous Programs
PLDI Research Papers
Bernhard Kragl IST Austria, Constantin Enea University of Paris Diderot, France, Thomas A. Henzinger IST Austria, Austria, Suha Orhun Mutluergil IRIF, France / University of Paris, France / CNRS, France, Shaz Qadeer Novi, USA