A Definition of Data Consistency Using Event Lattices

Abstract Replication of data is a common technique to enhance performance in distributed systems in which multiple activities use shared passive objects. If replicated data is updateable rather than read-only, modifications must be propagated to other copies of the replicated data in order to assure a consistent view. The delay of update propagations affects the observations of activities running on the different nodes of a distributed system. Read operations on the same passive object may return different values depending on the nodes they are executed on and the replica being accessed. A memory consistency model defines the legal ordering of data modifications issued by an activity on a node of the distributed system, as observed by remote activities. This paper presents a formal definition of the term data consistency using an event lattice model. With this definition the consistency of an arbitrary execution of a concurrent system can be determined