The complexity of verifying memory coherence and consistency
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.
testing shared memory hardware memory structures design styles reliability fault-tolerance error-checking theory of computation nonnumerical algorithms and problems sequencing and scheduling