The complexity of sequential consistency
Phillip B. Gibbons, Ephraim Korach · 2003
The authors explore the complexity of deciding whether an execution of a shared-memory multiprocessor is sequentially consistent. They present the first results showing the NP-completeness of this problem, even for short programs or small machines. They also explore possible augmentations to the memory system; a fast decision algorithm is presented for such an augmented shared memory. The results obtained demonstrate the difficulty in detecting when an execution of a memory system fails to be sequentially consistent, and supporting all possible sequentially consistent executions in hardware.>