Maximal serializability of iterated transactions. (English) Zbl 0572.68082

The serializability condition is usually considered in order to maintain the consistency of a Database in the presence of conflicting accesses to the Database performed by concurrent transactions. This serializability condition is considered herein as a general synchronization problem among transactions (or processes) which can be iterated infinitely often. The behaviour of such a system of transactions is represented by an infinite word over the alphabet of the operations performed by the transactions. Then a characterization of the prefixes of such behaviours satisfying the serializability condition - so-called correct behaviours - is given and it is shown that the set of all correct behaviours can be controlled by a finite automaton. As an example, the classical ’dining philosophers’ problem is shown to be entirely modelled and solved as a serializability problem.


68P20 Information storage and retrieval of data
68N25 Theory of operating systems
Full Text: DOI


[1] Bernstein, P.A.; Goodman, N., Concurrency control in distributed data base systems, Computing surveys, 13, 2, 185-221, (1981)
[2] Büchi, J., On a decision method in restricted second-order arithmetic, () · Zbl 0147.25103
[3] Cori, R.; Perrin, D., Sur la reconnaissabilite dans LES monoides partiellement commutatifs libres, (), 1, to appear
[4] Dijkstra, E.W., Hierarchical ordering of sequential process, Acta informatica, 1, 2, 115-138, (1971)
[5] Eswaran, K.P.; Gray, J.N.; Lorie, R.A.; Traiger, J.L., The notions of consistency and predicate locks in data base systems, Comm. ACM, 19, 11, 624-633, (1976) · Zbl 0341.68023
[6] Flé, M.P.; Roucairol, G., On serializability of iterated transactions, (), 194-200 · Zbl 0572.68082
[7] Karp, R.M.; Miller, R.E., Parallel program schemata, J. comput. system sci., 3, 147-195, (1969) · Zbl 0198.32603
[8] Keller, R.M., Parallel program schemata and maximal parallelism, J. assoc. comput. Mach., 20, 3, 514-537, (1973) · Zbl 0273.68011
[9] Papadimitriou, C.H.; Bernstein, P.A.; Rothnie, J.B., Some computational problems related to data base concurrency control, (), 272-282
[10] Roucairol, G., Mots de synchronization, RAIRO informatique/computer, 12, 4, 277-290, (1978) · Zbl 0387.68021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.