Tree-HP2PL: A Hierarchical Priority-Based Two-Phase Locking Protocol for Nested Transactions in Distributed Real-Time Database Systems
Abstract
Modern applications require advanced concurrency control protocols to efficiently manage nested transactions within Distributed Real-Time Database Systems (DRTDBS). This paper introduces Tree-HP2PL, a Hierarchical Priority-Based Two-Phase Locking protocol designed to optimize conflict resolution within nested transactions. The proposed method employs a binary search tree structure for transaction management and incorporates a hybrid strategy combining Depth-First Search (DFS) and parallel Breadth-First Search (BFS) for efficient lock acquisition. Tree-HP2PL is capable of distinguishing and resolving various conflict scenarios, including no conflict, intra-transaction conflicts, and inter-transaction conflicts. To mitigate pseudo-priority inversion, it implements priority inheritance and transaction abort mechanisms as necessary. The protocol’s effectiveness was evaluated through experimental simulations conducted in a MATLAB simulation environment, using transaction volumes ranging from 5 to 30 across 10 iterations. Results indicate that execution time remains efficient, with a recorded time of 0.0011 seconds for 5 transactions and showing controlled growth to 0.0049 seconds at 20 transactions. Memory usage demonstrated linear scalability, increasing from 0.006 MB at 5 transactions to 0.016 MB at 30 transactions. Although system throughput decreases under heavier transaction loads, it remains competitive, dropping from 1980 transactions per second (TPS) at 5 transactions to 998 TPS at 30 transactions. Notably, the success ratio consistently maintained a value of 100%, reflecting the protocol’s high reliability. In conclusion, Tree-HP2PL effectively addresses the challenges of concurrency control in nested transaction environments by offering a scalable, structured, and conflict-aware locking mechanism. Its robust performance and methodological design validate its applicability in real-time distributed systems, marking it as a significant improvement over existing flat or unstructured locking techniques.References
REFERENCES
T. C. a. C. E. Begg, Database Systems: A Practical Approach to Design, Implementation and Management, II, Ed., Boston, MA: Addison-Wesley Longman Publishing Co., Inc., 1998.
M. T. Ö. a. P. Valduriez, Principles of Distributed Database Systems, IV, Ed., Springer, 2020, pp. pp. 1-674.
K. Ramamritham, “Real-time databases,” Distributed and Parallel Databases, vol. 01, no. 02, pp. 199-226, 1993.
R. A. a. H. Garcia-Molina, “Scheduling Real-Time Transactions: A Performance Evaluation,” in 34th International Conference on Very Large Data Bases, 1988.
J. S. a. W. Zhao, “On real-time transactions,” in ACM SIGMOD , March 1988..
M. C. a. M. L. J. Haritsa, “Data Access Scheduling in Firm Real-Time Database Systems,” International Journal of Real-Time Systems, vol. 4, no. 3, 1992.
M. M. a. A. K. S. U. Shanker, “Distributed real-time database systems: Background and literature review,” International Journal of Distributed and Parallel Databases, vol. 23, no. 2, p. 127–149, 2008.
J. Gray, “A Transaction Model,” in ICALP, 1980.
J. Gray, “Notes on database operating systems,” in Lecture Notes in Computer Science,Operating Systems -- An Advanced Course, vol. 60, Berlin, Springer-Verlag, 1978, pp. 393-481.
J. Gray, “The recovery manager of the system R database manager,” ACM Computing Surveys, vol. 13, p. 223–244 , 1981.
S. M. Y. B. H. K. a. A. S. R. Rastogi, “On correctness of non-serializable executions,” in 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1993.
S. A. a. V. Vianu, “Equivalence and optimization of relational transactions,” Journal of the ACM, vol. 35, pp. 70-120, 1988.
J. Gray, “Why do computers stop and what can be done about it,” in CIPS (Canadian Information Processing Society) Edmonton '87 Conference Tutorial Notes, Edmonton, Canada, 1987.
C. H. Papadimitriou, “Serializability of concurrent database updates,” Journal of the ACM, vol. 26, no. 4, p. 631–653, 1979.
P. M. L. I. a. D. J. R. R. E. Stearns, “Concurrency controls for database systems,” in 17th Symposium on Foundations of Computer Science, 1976.
H. T. K. a. C. H. Papadimitriou, “An optimality theory of concurrency control for databases,” in ACM SIGMOD International Conference on Management of Data, 1979.
M. J. C. a. M. Livny, “Distributed Concurrency Control Performance: A Study of Algorithm, Distribution, and Replication,” in 14th VLDB Conference, Los Angeles, California, 1988.
Y. C. a. L. Gruenwald, “Research Issues for a Real-Time Nested Transaction Model,” in 2nd IEEE Workshop on Real-Time Applications, July 1994.
M. O. A. E. B. Medjahed, “Generalization of ACID Properties,” in Encyclopedia of Database Systems, Boston, MA, 2009.
H. G.-M. a. K. Salem, “Sagas,” in ACM SIGMOD International Conference on Management of Data, 1987.
M. R. a. A. Sheth, Specification and execution of transactional workflows, K. W, Ed., ACM Press/Addison-Wesley, 1995, p. 592–620.
C. Pu, “Superdatabases for composition of heterogeneous databases,” in 4th International Conference on Data Engineering, 1988.
A. Z. a. B. Bhargava, Flex Transactions, Ö. M. Liu L., Ed., Boston, MA: Springer, 2009.
J. E. B. Moss, “Nested Transactions: An Approach to Reliable Distributed Computing,” Cambridge, MA, , 1981.
G. W. a. H. Schek, “Multi-level transactions and open nested transactions,” 1991.
L. A. Bjork, “Recovery scenario for a DB/DC system,” in ACM Annual Conference, 1973.
C. T. Davies, “Recovery semantics for a DB/DC system,” in ACM Annual Conference, 1973.
R. Guerraoui, “Nested transaction: Reviewing the coherence contract,” Elsevier Sciences Journal, vol. 84, p. 161–172, 1995.
G. Karabatis, “Nested Transaction Models,” in Encyclopedia of Database Systems, New York, 2017.
A. Buchmann, “Open Nested Transaction Models,” in Encyclopedia of Database Systems, New York, 2016.
H. S. H. a. M. E. E.-S. A. A. EI-Sayed, “Effect of shaping characteristics on the performance of nested transactions,” Information and Software Technology, vol. 43, no. 10, pp. 579-590, 2001.
T. H. a. K. Rothermel, “Concurrency Control Issue in Nested Transactions,” VLDB J, vol. 2, no. 1, pp. 39-74, 1993.
P. A. B. a. N. Goodman, “Concurrency control in distributed database systems,” ACM Computing Surveys, vol. 13, no. 2, p. 185–222, 1981.
V. H. a. N. G. P. A. Bernstein, Concurrency Control and Recovery in Database Systems, Addison Wesley, 1987.
R. H. Thomas, “A majority consensus approach to concurrency control for multiple copy databases,” ACM Transactions on Database Systems, 1979.
H. T. K. a. J. T. Robinson, “On optimistic methods for concurrency control,” ACM Transactions on Database Systems, vol. 6, no. 2, p. 213–226, 1981.
J. N. G. R. A. L. a. I. L. T. K. P. Eswaran, “The notions of consistency and predicate locks in a database system,” Communications of the ACM, vol. 19, no. 11, p. 624–633, 1976.
P. A. A. a. J. D. Day, “A principle for resilient sharing of distributed resources,” in 2nd Int. Conf. on Software Engineering, 1976.
M. Stonebraker, “Concurrency control and consistency of multiple copies of data in distributed INGRES,” IEEE Transactions on Software Engineering, vol. 5, no. 3, pp. 188-194, May 1979.
B. L. a. R. O. C. Mohan, “Transaction management in the r* distributed database management system,” ACM Transactions on Database Systems, vol. 11, no. 4, p. 378–396, 1986.
Tandem, “Nonstop SQL – a distributed high-performance, high-availability implementation of SQL,,” in Int. Workshop on High-Performance Transaction Systems,, 1987.
Tandem, “A benchmark of NonStop SQL on the debit credit transaction,” in ACM SIGMOD Int. Conf. on Management of Data, 1988.
A. Borr, “High performance SQL through low-level system integration,” in ACM SIGMOD Int. Conf. on Management of Data, 1988.
D. H. a. J. P. Verjus, “An algorithm for maintaining the consistency of multiple copies,” in 1st Int. Conf. on Distributed Computing Systems, 1979.
D. P. Reed, “Naming and synchronization in a decentralized computer system,” Cambridge, Mass., Sept., 1978.
D. P. Reed, “Implementing Atomic Actions on Decentralized Data,” ACM Transactions on Computer Systems,, vol. 1, pp. 3-23, 1983.
D. B. a. B. Mahbod, “Generalized version control in an object-oriented database,” in IEEE 4th Int. Conf. Data Engineering, February, 1988.
H. T. C. a. W. Kim, “A unifying framework for versions in a CAD environment,” in Int. Conf. Very Large Data Bases, Kyoto, Japan, 1986.
H. T. C. a. W. Kim, “Versions and change notification in an object-oriented database system,” in Design Automation Conference, 1988.
B. K. a. K. Y. L. A. Chiu, “Comparing two-phase locking and optimistic concurrency control protocols in multiprocessor real-time databases,” in 5th International Workshop on Parallel and Distributed Real-Time Systems and 3rd Workshopon Object-Oriented Real-Time Systems, 1997.
M. C. a. M. L. R. Agrawal, “Concurrency Control Performance Modeling: Alternatives and Implications,” ACM Transactions on Database Systems, Dec. 1987.
K. R. a. S. C. J. A. Stankovic, “Evaluation of a Flexible Task Scheduling Algorithm for Distributed Hard Real-Time Systems,” IEEE Transactions on Computers, vol. 34, no. 12, pp. 1130-1143, Dec. 1985.
J. L. P. a. A. Silberschatz, Operating System Concepts, Addison-Wesley Publishing Company, 1985.
J. A. S. a. D. T. J. Huang, “On using priority inheritance in real-time databases,” in Twelfth. IEEE Real-Time Systems Symposium, 1991.
S. D. a. L. Sha, “Sources of Unbounded Priority Inversion in Real-Time Systems and a Comparative Study of Possible Solutions,” ACM Operating Systems Review, p. 110–120, 1992.
W. u. Haque, “Transaction Processing in Real-Time Database Systems,” 1993.
N. Lynch, “Concurrency control for resilient nested transactions,” Advances in Computing Research, vol. 3, p. 335–376, 1986.
N. L. a. M. Merrit, “Introduction to the theory of nested transactions,” Cambridge, Mass, 1986.
N. L. M. M. a. W. E. W. A. Fekete, “Nested transactions and read/write locking,” in 6th ACM Symposium on Principles of Database Systems, San Diego, CA, 1987.
J. K. L. a. A. Fekete, “Multi-granularity locking for nested transaction systems,” in MFDBS'91, 1991.
N. L. M. M. a. W. E. W. A. Fekete, “Commutativity-based locking for nested transactions,” Journal of System Sciences, vol. 41, p. 65–156, 1990.
S. N. M. a. B. C. S. K. Madria, “Formalization and correctness of a concurrency control algorithm for an open and safe nested transaction model using I/O automaton model,” in 8th International Conference on Management of Data (COMAD'97), Madras, India, 1997.
F. R. a. T. Harder, “Concurrency control in nested transactions with enhanced lock modes for KBMSs,” in 6th International Conference on Database and Expert Systems Applications (DEXA'95), London, UK,, 1995.
K. G. a. N. Lynch, “Nested transactions and quorum consensus,” ACM Transactions on Database Systems, vol. 19, p. 537–585, 1994.
A. F. a. T. Kameda, “Concurrency control of nested transactions accessing B-trees,” in 8th ACM Symposium on Principles of Database Systems, 1989.
S. N. M. a. B. C. S. K. Madria, “Formalization of linear hash structures using nested transactions and I/O automaton model,” in IADT 98, Berlin, Germany, 1997.
B. S. L. A. a. A. M. A. M. Abdouli, “A System Supporting Nested Transactions in DRTDBSs,” in 1st International High-Performance Computing, September 2005.
B. S. A. Majed Abdouli, “Scheduling distributed real-time nested transactions,” in IEEE ISORC, IEEE Computer Society, 2005.
J. H. a. K. Ramamritham, “The prompt real-time commit protocol,” IEEE Transactions on Parallel and Distributed Systems, 2000.
K. R. Theo Haerder, “Concepts for transaction recovery in nested transactions,” in ACM SIGMOD, 1987.
T. H. A. G. a. J. L. R. F. Resende, “Detection arcs for deadlock management in nested transactions and their performance,” in Advances in Databases, BNCOD ,Lecture Notes in Computer Science,Springer, Berlin,Heidelberg, 1997.
W. u. Haque, Transaction Processing in Real-Time Database Systems, 1993.
DOI:
https://doi.org/10.31449/inf.v50i8.8105Downloads
Published
How to Cite
Issue
Section
License
Authors retain copyright in their work. By submitting to and publishing with Informatica, authors grant the publisher (Slovene Society Informatika) the non-exclusive right to publish, reproduce, and distribute the article and to identify itself as the original publisher.
All articles are published under the Creative Commons Attribution license CC BY 3.0. Under this license, others may share and adapt the work for any purpose, provided appropriate credit is given and changes (if any) are indicated.
Authors may deposit and share the submitted version, accepted manuscript, and published version, provided the original publication in Informatica is properly cited.
