Reconciling Preemption Bounding with DPOR

Abstract

Abstract There are two major techniques for scaling up stateless model checking: dynamic partial order reduction (DPOR), which only explores executions that differ in the ordering of racy accesses, and preemption bounding , which only explores executions containing up to k preemptions (preemptive context-switches). Combining these two techniques is challenging because DPOR-equivalent executions often contain a different number of preemptions, making it incorrect to cut explorations that exceed the preemption bound. To restore completeness, prior work has weakened the DPOR algorithm, which often results in the exploration of many redundant executions. We propose an alternative approach. Starting from an optimal DPOR algorithm, we achieve completeness by allowing some slack on the preemption-bound of the explored executions. We prove that the required slack does not exceed the number of threads of the program (minus two), and that this upper limit is tight.