Verifying sequential consistency with at most π preemptions is polynomial-time for single-writer programs, NP-hard for two-writer programs, and has an ETH-based conditional lower bound for three-writer programs.
Title resolution pending
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
years
2026 3verdicts
UNVERDICTED 3representative citing papers
VerCors-relaxed encodes SLR logic to automatically verify weak memory concurrent programs with realistic performance on literature examples.
Consistency testing for release-acquire C11 is in P with one writer per location but NP-hard with two writers and ETH-hard for subexponential time with three writers.
citing papers explorer
-
Verifying Sequential Consistency under Bounded Preemptions
Verifying sequential consistency with at most π preemptions is polynomial-time for single-writer programs, NP-hard for two-writer programs, and has an ETH-based conditional lower bound for three-writer programs.
-
Deductive Verification of Weak Memory Programs with View-based Protocols (extended version)
VerCors-relaxed encodes SLR logic to automatically verify weak memory concurrent programs with realistic performance on literature examples.
-
Complexity of Consistency Testing for the Release-Acquire Semantics
Consistency testing for release-acquire C11 is in P with one writer per location but NP-hard with two writers and ETH-hard for subexponential time with three writers.