The Complexity of Sequential Consistency

Sequential consistency is the most-widely used correctness condition for a multiprocessor memory system. In a sequentially consistant memory, each execution is indistinguishable (by the processors) from an execution of serial memory in which only one read or write occurs at a time. Given a sequence of shared memory reads and writes for each processor, the Verifying Sequential Consistency (VSC) problem is to determine whether or not the collection of sequences is possible on a sequentially consistent memory, i.e. the sequences can be merged into a total order consistent with the values read and written. This problem arises in the context of executing (possibly buggy) parallel programs on high-performance sheared memory multiprocessors.