Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Fair serializability of iterated transactions using fifo-nets

M. P. Flé1 and G. Roucairol1

(1)  Laboratoire de Recherche en Informatique Unité Associée 410 du CNRS Bâtiment 490, Université de Paris-Sud, 91405 Orsay Cedex, France
Abstract
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. 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 guaranties 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.

Key words  concurrency - maximal serializability - fair - Petri-nets (FIFO-Nets)

Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.110 • Server: mpweb02
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)