Introduction
Analyzing concurrent systems is a significant challenge due to the state-space explosion caused by the vast number of possible event interleavings. This complexity is exacerbated by weak memory architectures, such as those in modern CPUs, which allow instruction reordering for performance. While symbolic techniques using SAT/SMT solvers are effective for bounded model checking (BMC), they often suffer from scalability issues—specifically, cubic constraint complexity—and a lack of formal grounding in abstract algebraic concurrency theories. This paper addresses these gaps by providing a theoretical foundation for handling loops and introducing a quadratic-size symbolic encoding for weak memory models.
Methodology: Partial String Theory and Refinement
The authors model program executions using Partial String Theory, a variant of partially ordered multisets (pomsets). A central concept is the definition of program refinement through "monotonic bijective morphisms." This allows for a formal comparison between different execution orders, where one partial string $x$ is said to refine another $y$ ($x \sqsubseteq y$) if it preserves labels while potentially adding ordering constraints.
To handle non-determinism, such as branching logic, programs are represented as downward-closed sets of partial strings using a Hoare powerdomain construction. Furthermore, the paper addresses program loops through a least fixed point reduction. Theorem 2 proves that an infinite number of potential events in a loop can be reduced to a finite, bounded set for decision procedures, exploiting the periodicity of repeated program segments.
Complexity Breakthrough: From Cubic to Quadratic
A major contribution of this work is the reduction of symbolic encoding complexity. Traditional "from-read" axioms in weak memory models typically require checking triples of events (a read and two writes), leading to $O(N^3)$ constraints relative to the number of memory accesses $N$.
The authors identify that this can be optimized by encoding the least upper bound of a set of store events. By introducing a new symbolic variable for each "acquire" event to represent this bound, the need for cubic cross-referencing is eliminated. This results in a quadratic-size ($O(N^2)$) symbolic encoding, offering a significant asymptotic improvement for verification tools like CBMC.
Key Results and Theoretical Implications
The paper establishes several critical results:
- NP-Completeness: The Partial String Refinement (PSR) problem is proven to be NP-complete, justifying the application of high-performance SAT/SMT solvers.
- Semantic Equivalence: The partial order model is shown to be a valid model for Concurrent Kleene Algebra (CKA), satisfying fundamental laws such as the exchange law.
- Axiomatic Mapping: The "SC-relaxed" (relaxed sequential consistency) semantics are mapped to three standard weak memory axioms: write coherence, from-read, and global read-from.
Conclusion and Future Work
By bridging the gap between abstract algebra (CKA) and practical verification, this work provides both a formal justification for existing partial order techniques and a path toward more scalable tools. Future research will focus on extending the $O(N^2)$ encoding to even weaker memory models like PowerPC or ARM and conducting extensive experimental validation against existing cubic encodings in live BMC environments.
Summary updated