A Suite of Formal Definitions for Consistency Criteria in Distributed Shared Memories
Michel Raynal, A. Schiper · 1996
A shared memory built on top of a distributed system constitutes a Distributed Shared Memory (DSM). If a lot of protocols implementing DSMs in various contexts have been proposed, no set of homogeneous definitions has been given for the many semantics offered by these implementations. This paper provides a suite of such definitions for atomic, sequential, causal, PRAM and a few others consistency criteria. These definitions are based on a unique framework: a parallel computation is defined as a partial order on the set of read and write operations invoked by processes, and a consistency criterion is defined as a constraint on this partial order. Such an approach provides a simple classification of consistency criteria, from the more to the less constrained one. This paper can also be considered as a survey on consistency criteria for DSMs. Key words: shared memory, distributed system, consistency criteria, partial order. 1 Introduction Since the end of the eighties, the Distributed S...