DSpace
 

EPrints@IIT Delhi >
Faculty Research Publicatons  >
Mathematics >

Please use this identifier to cite or link to this item: http://eprint.iitd.ac.in/handle/2074/945

Title: Virtual partition algorithm in a nested transaction environment and its correctness
Authors: Madria, Sanjay Kumar
Maheshwari, S N
Chandra, B
Keywords: Virtual partition algorithm
Nested transaction
Data replication
Quorum consensus
Reorder serializability
Issue Date: 2001
Citation: Information Sciences, 137(1-4), 211-244
Abstract: In this paper, we present a formal description of the virtual partition algorithm in a nested transaction environment and prove its correctness. We model the virtual partition algorithm in a nested transaction environment using the I/O automaton model. The formal description is used to construct a complete correctness proof that is based on standard assertional techniques and on a natural correctness condition, and takes advantage of the modularity that arises from describing the algorithm as nested transactions. Our presentation and proof treat issues of data replication entirely separately from issues of concurrency control. Moreover, we have identified that the virtual partition algorithm cannot be proven correct in the sense of Goldman's work [ACM Trans. Database Syst. 19(4) (1994) 537] on Gifford's quorum consensus algorithm using the serializability theorem defined by Fekete et al. [Atomic Transactions, Morgan-Kaufmann, USA, 1994]. Thus, we have stated a weaker notion of correctness conditions, which we call the reorder serializability theorem. We have shown that not all classes of replication algorithms can be proven in the way Goldman has presented the proof of Gifford's quorum consensus algorithm.
URI: http://eprint.iitd.ac.in/dspace/handle/2074/945
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
madriavir2001.pdf933.36 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback