Truly stateless, optimal dynamic partial order reduction
Top Cited Papers
Open Access
- 12 January 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (POPL) , 1-28
Abstract
Dynamic partial order reduction (DPOR) verifies concurrent programs by exploring all their interleavings up to some equivalence relation, such as the Mazurkiewicz trace equivalence. Doing so involves a complex trade-off between space and time. Existing DPOR algorithms are either exploration-optimal (i.e., explore exactly only interleaving per equivalence class) but may use exponential memory in the size of the program, or maintain polynomial memory consumption but potentially explore exponentially many redundant interleavings. In this paper, we show that it is possible to have the best of both worlds: exploring exactly one interleaving per equivalence class with linear memory consumption. Our algorithm, TruSt, formalized in Coq, is applicable not only to sequential consistency, but also to any weak memory model that satisfies a few basic assumptions, including TSO, PSO, and RC11. In addition, TruSt is embarrassingly parallelizable: its different exploration options have no shared state, and can therefore be explored completely in parallel. Consequently, TruSt outperforms the state-of-the-art in terms of memory and/or time.Keywords
Funding Information
- ERC (101003349)
This publication has 32 references indexed in Scilit:
- Owicki-Gries Reasoning for Weak Memory Models2015
- Dynamic partial order reduction for relaxed memory models2015
- Stateless Model Checking for TSO and PSO2015
- Herding CatsACM Transactions on Programming Languages and Systems, 2014
- x86-TSOCommunications of the ACM, 2010
- Software Model Checking: The VeriSoft ApproachFormal Methods in System Design, 2005
- Dynamic partial-order reduction for model checking software2005
- Model checking for programming languages using VeriSoft1997
- Efficient and correct execution of parallel programs that share memoryACM Transactions on Programming Languages and Systems, 1988
- Trace theory1987