Precedence-based memory models

This paper presents a general framework for understanding precedence-based memory models, which are generalizations of standard multiprocessor models. Precedence-based models need not mention pro-cesses explicitly, and can express any conditions that rely only on some operations being required to precede other operations. We dene a gen-eralized notion of sequential consistency and per-location sequential con-sistency in this framework, and we analyze the Backer algorithm used in the Cilk system [3], showing that it implements per-location sequential consistency. We also give conditions under which client processes cannot distinguish a per-location sequentially consistent memory from a sequen-tially consistent one