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

Full metadata record

DC FieldValueLanguage
dc.contributor.authorMadria, Sanjay Kumar-
dc.contributor.authorMaheshwari, S N-
dc.contributor.authorChandra, B-
dc.identifier.citationInformation Sciences, 137(1-4), 211-244en
dc.description.abstractIn 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.en
dc.format.extent955760 bytes-
dc.subjectVirtual partition algorithmen
dc.subjectNested transactionen
dc.subjectData replicationen
dc.subjectQuorum consensusen
dc.subjectReorder serializabilityen
dc.titleVirtual partition algorithm in a nested transaction environment and its correctnessen
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