×

Fair serializability of iterated transactions using FIFO-nets. (English) Zbl 0562.68018

Advances in Petri nets 1984, Lect. Notes Comput. Sci. 188, 154-168 (1985).
Summary: [For the entire collection see Zbl 0556.00014.]
The serializability condition is usually considered in order to maintain the consistency of a database in the presence of conflicting accesses to the data-base performed by concurrent transactions. The transactions considered in this paper may be infinitely often repeated and a synchronization algorithm is proposed which controls the serializability condition for such transactions. This algorithm, based upon the use of FIFO-nets, provides the maximal amount of parallelism among the transactions and guarantees fairness, i.e., every transaction is actually performed infinitely often. As an application, the synchronization algorithm is shown to give also a fair solution to the classical dining philosophers problem. The size of the memory needed by the algorithm cannot be bounded, however a particular case is pointed out for which memory boundedness can be achieved. This particular case covers the problem of updating multiple copies of a database.

MSC:

68N25 Theory of operating systems
68P20 Information storage and retrieval of data
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Citations:

Zbl 0556.00014