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, (Internat. Congress Logic Method Phil. Sci. (1962), Standford Univ. Press) · Zbl 0147.25103
[3] Cori, R.; Perrin, D., Sur la reconnaissabilite dans les monoides partiellement commutatifs libres, (RAIRO Inform. Théorique (1984), Université de Bordeaux), 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, (ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing. ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, Ottawa, Canada (1982)), 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, (Proc. Conf. on Theoretical Computer Science. Proc. Conf. on Theoretical Computer Science, Waterloo, Canada (1977)), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.