The complexity of verifying memory coherence and consistency
Jason F. Cantin, Mikko H. Lipasti, James E. Smith · IEEE Transactions on Parallel and Distributed Systems · 2005
The problem of testing shared memories for memory coherence and consistency is studied. First, it is proved that detecting violations of coherence in an execution is NP-complete, and it remains NP-complete for a number of restricted instances. This result leads to a proof that all known consistency models are NP-hard to verify. The complexity of verifying consistency models is not a mere consequence of coherence, and verifying sequential consistency remains NP-complete even after coherence has been verified.