Maximal serializability of iterated transactions. (English) Zbl 0572.68082

Flé, M. P.; Roucairol, G.

Theor. Comput. Sci. 38, 1-16 (1985).

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.

MSC:

68P20	Information storage and retrieval of data
68N25	Theory of operating systems

Keywords:

database consistency; conflicting accesses; concurrent transactions; synchronization; infinite word; finite automaton; dining philosophers

References:

[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