|
EPrints@IIT Delhi >
Faculty Research Publicatons >
Mathematics >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/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 correctn... |
| URI: | http://eprint.iitd.ac.in/dspace/handle/2074/945 |
| Appears in Collections: | Mathematics
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| madriavir2001.pdf | | 933Kb | Adobe PDF | View/Open |
|
Show full item record
All items in DSpace are protected by copyright, with all rights reserved.
|
