|
EPrints@IIT Delhi >
Faculty Research Publicatons >
Mathematics >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/2074/915
|
| Title: | Formalization and correctness of a concurrent linear hash structure algorithm using nested transactions and I/O |
| Authors: | Madria, Sanjay Kumar
Maheshwari, S N |
| Keywords: | Nested transaction
Linear hash structure
I/O automaton model
Lock-coupling
Serially correct
Client–server |
| Issue Date: | 2001 |
| Citation: | Data & Knowledge Engineering, 37(2), 139-176 |
| Abstract: | In this paper, we formalize and prove the correctness of a nested transaction version of the concurrency control algorithm using a linear hash structure. Nested transactions allow increased parallel execution of transactions, and handle transaction aborts in our system. We present our nested transaction model in a linear hash structure environment using a well-known I/O automaton model. We have modeled both the buckets and the transactions as I/O automata. In our algorithm, the locks have been considered at both key and vertex level. These locks have been implemented in a nested transaction environment using Moss's two phase locking algorithm and the locking protocols of the linear hash structure algorithm with a lock coupling technique. We have proved that our linear hash structure algorithm in a nested transaction environment is ‘serially correct'. We have discussed briefly the client–server architecture for the implementation of our system. |
| URI: | http://eprint.iitd.ac.in/dspace/handle/2074/915 |
| Appears in Collections: | Mathematics
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| madriafor2001.pdf | | 1421Kb | Adobe PDF | View/Open |
|
Show full item record
All items in DSpace are protected by copyright, with all rights reserved.
|
