Verifying distributed programs via canonical sequentialization
Open Access
- 12 October 2017
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 1 (OOPSLA) , 1-27
Abstract
We introduce canonical sequentialization, a new approach to verifying unbounded, asynchronous, message-passing programs at compile-time. Our approach builds upon the following observation: due the combinatorial explosion in complexity, programmers do not reason about their systems by case-splitting over all the possible execution orders. Instead, correct programs tend to be well-structured so that the programmer can reason about a small number of representative executions, which we call the program’s canonical sequentialization. We have implemented our approach in a tool called Brisk that synthesizes canonical sequentializations for programs written in Haskell, and evaluated it on a wide variety of distributed systems including benchmarks from the literature and implementations of MapReduce, two-phase commit, and a version of the Disco distributed file-system. We show that unlike model checking, which gets prohibitively slow with just 10 processes Brisk verifies the unbounded versions of the benchmarks in tens of milliseconds, yielding the first concurrency verification tool that is fast enough to be integrated into a design-implement-check cycle.Keywords
This publication has 51 references indexed in Scilit:
- A Logic-Based Framework for Verifying Consensus Algorithms2014
- On Solving Universally Quantified Horn Clauses2013
- Automatic Verification of Erlang-Style Concurrency2013
- Parameterised Multiparty Session TypesLogical Methods in Computer Science, 2012
- Automatic formal verification of MPI-based parallel programsACM SIGPLAN Notices, 2011
- A calculus of atomic actionsACM SIGPLAN Notices, 2009
- Efficient Verification of Halting Properties for MPI Programs with Wildcard Receives2005
- Better verification through symmetryFormal Methods in System Design, 1996
- The existence of refinement mappingsTheoretical Computer Science, 1991
- ReductionCommunications of the ACM, 1975