State Space Estimation for DPOR-based Model Checkers
Analysis
This paper addresses the challenging problem of estimating the size of the state space in concurrent program model checking, specifically focusing on the number of Mazurkiewicz trace-equivalence classes. This is crucial for predicting model checking runtime and understanding search space coverage. The paper's significance lies in providing a provably poly-time unbiased estimator, a significant advancement given the #P-hardness and inapproximability of the counting problem. The Monte Carlo approach, leveraging a DPOR algorithm and Knuth's estimator, offers a practical solution with controlled variance. The implementation and evaluation on shared-memory benchmarks demonstrate the estimator's effectiveness and stability.
Key Takeaways
- •Addresses the #P-hard problem of counting Mazurkiewicz trace-equivalence classes in concurrent programs.
- •Proposes a poly-time unbiased estimator based on a Monte Carlo approach using a DPOR algorithm and Knuth's estimator.
- •Employs stochastic enumeration to control variance.
- •Demonstrates stable and accurate estimates on shared-memory benchmarks.
- •Provides a valuable tool for predicting model checking runtime and resource allocation.
“The paper provides the first provable poly-time unbiased estimators for counting traces, a problem of considerable importance when allocating model checking resources.”