Serialization of concurrent programs

摘要

The serializability condition is usually considered in order to maintain the consistency of a data base in the presence of conflicting accesses to the data base performed by concurrent transactions. The usual notion of a transaction is generalized in two ways; a transaction is given by a possibly infinite set of sequences of operations (this set may be interpreted as the possible execution traces of a program) and a transaction can be arbitrariy often repeated. A concurrent computat on of such a system of transactions is represented by a word formed by interleaving execution traces of the transactions. The standard serializability criterion is extended to this model and it is shown that for regular transactions the set of serializable computations is regular.