Flé, M. P.; Roucairol, G. 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. Cited in 5 Documents 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.) Keywords:database; conflicting accesses; concurrent transactions; synchronization algorithm; serializability condition; FIFO-nets; fairness; dining philosophers; memory boundedness Citations:Zbl 0556.00014 PDFBibTeX XML