Concurrency control for distributed real-time databases

ABSTRACT

The concurrency control of transactions in a real-time database must satisfy not only the consistency constraints of the database but also the timing constraints of individual transactions. In this paper, we present a real-time concurrency control protocol that can be used in a distributed and decomposable real-time database. The protocol is based on the integration of a modular concurrency control theory with a real-time scheduling protocol called the priority ceiling protocol. This protocol supports the replication of data objects and avoids the formation of deadlocks. Finally, an analysis of the performance of this protocol is presented.

REFERENCES

• 1: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 2: Hector Garcia-Molina, Using semantic knowledge for transaction processing in a distributed database, ACM Transactions on Database Systems (TODS), v.8 n.2, p.186-213, June 1983 [doi>10.1145/319983.319985]
• 3: H. T. Kung , C. H. Papadimitriou, An optimality theory of concurrency control for databases, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582114]
• 4: John P. Lehoczky , Lui Sha, Performance of real-time bus scheduling algorithms, ACM SIGMETRICS Performance Evaluation Review, v.14 n.1, p.44-53, May 1986
• 5: [5] Lehoczky, J. P., Sha, L. and Ding, Y. The Rate Monotonic Scheduling Algorithm -- Exact Charaterization and Average Case Behavior. Technical Report, Department of Statistics, Carnegie-Mellon University, 1987.
• 6: [6] Lehoczky, J. P., Sha, L. and Strosnider, J. Enhancing Aperiodic Responsiveness in A Hard Real-Time Environment. IEEE Real-Time System Symposium, 1987.
• 7: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 8: Nancy A. Lynch, Multilevel atomicity—a new correctness criterion for database concurrency control, ACM Transactions on Database Systems (TODS), v.8 n.4, p.484-502, Dec. 1983 [doi>10.1145/319996.319999]
• 9: Peter Martin Schwarz, Transactions on typed objects, Carnegie Mellon University, Pittsburgh, PA, 1984
• 10: [10] Sha, L., Rajkumar, R. and Lehoczky, J. P. Priority Inheritance Protocols: An Approach to Real-Time Synchronization. Technical Report (CMU-CS-87-181), Department of Computer Science, CMU, 1987.
• 11: [11] Sha, L., Rajkumar, R. and Lehoczky, J. P. Task Scheduling in Distributed Real-Time Systems. Proceedings of IEEE Industrial Electronics Conference, 1987.
• 12: Lui Sha , John Lehoczky , E. Douglas Jensen, Modular Concurrency Control and Failure Recovery, IEEE Transactions on Computers, v.37 n.2, p.146-159, February 1988 [doi>10.1109/12.2144]
• 13: [13] Sha, L., Rajkumar, R. and Lehoczky, J. P. Concurrency Control for Real-Time Databases. Technical Report, Department of Computer Science, 1988.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Management, Performance, Theory, Verification