Multiserialization of iterated transactions (Q797005)

In the case of concurrent accesses to a data base, the serializability criterion is generally considered as the right one in order to maintain the consistency of the entities of the data base. As a matter of fact, if one considers transactions operating on a data base such that every transaction preserves individually the consistency property to be satisfied, then so does any sequential composition of these transactions and then so does any serializable behaviour, i.e., any behaviour in some sense equivalent to a sequential composition of the transactions. The equivalence which is generally used is such that two behaviours are said to be equivalent if the relative ordering of so-called conflicting operations is the same in both behaviours (in data base systems, conflicts are deduced from the way operations of different transactions access to shared data). In this paper, the serializability criterion is generalized in two directions. In behaviours, transactions can be iterated an arbitrarily large number of times as might behave processes in an operating system. On the other hand, this criterion appears too strong in various cases, the consistency property being preserved by non serializable behaviours. A new criterion, the multiserializability criterion is introduced: being given several relations of conflict, a behaviour is said to be multiserializable if it is serializable for each of these conflict relations. For transaction systems controlled under the multiserializability criterion, a characterization of deadlock freedom is given. Moreover, it is shown that every mutual exclusion problem can be presented as a multiserialization problem.