On the Definition of Sequential Consistency

Abstract

The definition of sequential consistency is compared with an intuitive notion of correctness. That the definition is not strong enough is illustrated through a hypothetical memory system which is clearly incorrect, yet sequentially consistent. It is claimed that the reason for this is the absence of a relation between what actually happens (temporal order) and what seems to happen (logical order). A stronger version of sequential consistency is proposed. (c) 2005 Elsevier B.V. All rights reserved.