Wu, Jiang; Manivannan, D.; Thuraisingham, Bhavani Necessary and sufficient conditions for transaction-consistent global checkpoints in a distributed database system. (English) Zbl 1193.68101 Inf. Sci. 179, No. 20, 3659-3672 (2009). Summary: Checkpointing and rollback recovery are well-known techniques for handling failures in distributed systems. The issues related to the design and implementation of efficient checkpointing and recovery techniques for distributed systems have been thoroughly understood. For example, the necessary and sufficient conditions for a set of checkpoints to be part of a consistent global checkpoint has been established for distributed computations. In this paper, we address the analogous question for distributed database systems. In distributed database systems, transaction-consistent global checkpoints are useful not only for recovery from failure but also for audit purposes. If each data item of a distributed database is checkpointed independently by a separate transaction, none of the checkpoints taken may be part of any transaction-consistent global checkpoint. However, allowing individual data items to be checkpointed independently results in non-intrusive checkpointing. In this paper, we establish the necessary and sufficient conditions for the checkpoints of a set of data items to be part of a transaction-consistent global checkpoint of the distributed database. Such conditions can also help in the design and implementation of non-intrusive checkpointing algorithms for distributed database systems. MSC: 68P15 Database theory 68M14 Distributed systems Keywords:checkpointing; recovery; distributed databases PDFBibTeX XMLCite \textit{J. Wu} et al., Inf. Sci. 179, No. 20, 3659--3672 (2009; Zbl 1193.68101) Full Text: DOI References: [1] A. Deshpande, J.M. Hellerstein, Decoupled query optimization for federated database systems, in: Proceedings of 18th International Conference on Data Engineering, 2002, pp. 716-727.; A. Deshpande, J.M. Hellerstein, Decoupled query optimization for federated database systems, in: Proceedings of 18th International Conference on Data Engineering, 2002, pp. 716-727. [2] Agbaria, Adnan; Friedman, Roy, Model-based performance evaluation of distributed checkpointing protocols, Performance Evaluation, 65, 5, 341-365 (2008) [3] Baldoni, Roberto; Hélary, Jean-Michel; Mostéfaoui, Achour; Raynal, Michel, Impossibility of scalar clock-based communication-induced checkpointing protocols ensuring the rdt property, Information Processing Letters, 80, 2, 105-111 (2001) · Zbl 1032.68009 [4] Baldoni, R.; Quaglia, F.; Raynal, M., Consistent checkpointing for transaction systems, The Computer Journal, 44, 2, 92-100 (2001) · Zbl 0982.68096 [5] Elmasri, R.; Navathe, S. B., Fundamentals of Database Systems (2007), Addison-Wesley · Zbl 0722.68035 [6] G. Ferran, Distributed checkpointing in a distributed data management system, in: Proceedings of the Real-Time Systems Symposium, Miami Beach, Florida, 1981, pp. 43-49.; G. Ferran, Distributed checkpointing in a distributed data management system, in: Proceedings of the Real-Time Systems Symposium, Miami Beach, Florida, 1981, pp. 43-49. [7] Garcia-Molina, H.; Salem, K., Main memory database systems: an overview, IEEE Transactions on Knowledge and Data Engineering, 4, 6, 509-516 (1992) [8] Hélary, Jean-Michel; Mostéfaoui, Achour; Raynal, Michel, Communication-induced determination of consistent snapshots, IEEE Transactions on Parallel and Distributed Systems, 10, 9, 865-877 (1999) [9] Hélary, Jean-Michel; Mostéfaoui, A.; Netzer, R. H.B.; Raynal, M., Communication-based prevention of useless checkpoints in distributed computations, Distributed Computing, 13, 1, 29-43 (2000) · Zbl 1448.68107 [10] Hagmann, R. B., A crash recovery scheme for a memory-resident database system, IEEE Transactions on Computers, 35, 9, 839-843 (1986) [11] Jungkee Kim, Geoffrey Fox, Scalable hybrid search on distributed databases, in: Proceedings of International Conference on Computational Science, vol. 3, 2005, pp. 431-438.; Jungkee Kim, Geoffrey Fox, Scalable hybrid search on distributed databases, in: Proceedings of International Conference on Computational Science, vol. 3, 2005, pp. 431-438. · Zbl 1120.68400 [12] Jim Kleewein, Practical issues with commercial use of federated databases. in: Proceedings of the 22th International Conference on Very Large Data Bases, 1996, p. 580.; Jim Kleewein, Practical issues with commercial use of federated databases. in: Proceedings of the 22th International Conference on Very Large Data Bases, 1996, p. 580. [13] Kumar, Vijay; Moe, Shawn D., Performance of recovery algorithms for centralized database management systems, Information Sciences, 86, 1, 101-147 (1995) [14] H. Kuss, On totally ordering checkpoints in distributed databases, in: Proceedings of the ACM SIGMOD International Conference on Management of Data, 1982, pp. 174-174.; H. Kuss, On totally ordering checkpoints in distributed databases, in: Proceedings of the ACM SIGMOD International Conference on Management of Data, 1982, pp. 174-174. [15] A.-P. Liedes, A. Wolski, SIREN: a memory-conserving, snapshot-consistent checkpoint algorithm for in-memory databases, in: Proceedings of the 22nd International Conference on Data Engineering, 2006, pp. 99-99.; A.-P. Liedes, A. Wolski, SIREN: a memory-conserving, snapshot-consistent checkpoint algorithm for in-memory databases, in: Proceedings of the 22nd International Conference on Data Engineering, 2006, pp. 99-99. [16] Lin, J.; Dunham, M. H., A survey of distributed database checkpointing, Distributed Parallel Databases, 5, 289-319 (1997) [17] Yi Luo, D. Manivannan, Fine: a fully informed and efficient communication-induced checkpointing protocol, in: IEEE Proceedings of the 3rd International Conference on Systems (ICONS’08), IEEE Computer Society, Los Alamitos, CA, USA, 2008, pp. 16-22.; Yi Luo, D. Manivannan, Fine: a fully informed and efficient communication-induced checkpointing protocol, in: IEEE Proceedings of the 3rd International Conference on Systems (ICONS’08), IEEE Computer Society, Los Alamitos, CA, USA, 2008, pp. 16-22. [18] Manivannan, D.; Jiang, Q.; Yang, Jianchang; Singhal, M., A quasi-synchronous checkpointing algorithm that prevents contention for stable storage, Information Sciences, 178, 15, 3110-3117 (2008) [19] Manivannan, D.; Singhal, Mukesh, Quasi-synchronous checkpointing: models, characterization, and classification, IEEE Transactions on Parallel and Distributed Systems, 10, 7, 703-713 (1999) [20] Muilu, Juha; Peltonen, Leena; Litton, Jan-Eric, The federated database a basis for biobank-based post-genome studies integrating phenome and genome data from 600000 twin pairs in Europe, European Journal of Human Genetics, 15, May, 718-723 (2007) [21] Netzer, Robert H. B.; Xu, Jian, Necessary and sufficient conditions for consistent global snapshots, IEEE Transactions on Parallel and Distributed Systems, 6, 2, 165-169 (1995) [22] S. Pilarski, T. Kameda, A novel checkpointing scheme for distributed database systems, in: Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Nashville, TN, 1990, pp. 368-378.; S. Pilarski, T. Kameda, A novel checkpointing scheme for distributed database systems, in: Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Nashville, TN, 1990, pp. 368-378. [23] Pilarski, S.; Kameda, T., Checkpointing for distributed databases: starting from the basics, IEEE Transactions on Parallel and Distributed Systems, 3, 602-610 (1992) [24] Pu, C., On-the-fly, incremental, consistent reading of entire databases, (Proceedings of the 11th Conference on Very Large Database (1985), Morgan Kaufman Publishers: Morgan Kaufman Publishers Los Altos, CA, Stockholm), 367-375 [25] K. Salem, H. Garcia-Molina, Checkpointing memory-resident databases, in: Proceedings of the Fifth International Conference on Data Engineering, 1989, pp. 452-462.; K. Salem, H. Garcia-Molina, Checkpointing memory-resident databases, in: Proceedings of the Fifth International Conference on Data Engineering, 1989, pp. 452-462. [26] Sheth, Amit P.; Larson, James E., Federated database systems for managing distributed heterogeneous and autonomous databases, ACM Computing Surveys, 22, 3, 183-286 (1990), September [27] Silberschatz, A.; Korth, H. F.; Sudarshan, S., Database System Concepts (2005), McGraw-Hill Publishing Co. [28] Singhal, M.; Shivaratri, N. G., Advanced Concepts in Operating Systems (1994), McGraw-Hill [29] Son, S. H.; Agrawala, A. K., Distributed checkpointing for globally consistent states of databases, IEEE Transactions on Software Engineering, 15, 10, 1157-1167 (1989) [30] Son, S. H., An algorithm for non-interfering checkpoints and its practicality in distributed database systems, Information Systems, 14, 5, 421-429 (1989) [31] J.L. Zhao, A. Segev, A. Chatterjee, A universal relation approach to federated database management, in: Proceedings of 11th International Conference on Data Engineering, 1995, pp. 261-270.; J.L. Zhao, A. Segev, A. Chatterjee, A universal relation approach to federated database management, in: Proceedings of 11th International Conference on Data Engineering, 1995, pp. 261-270. [32] Leon Zhao, J., Schema coordination in federated database management: a comparison with schema integration, Decision Support Systems, 20, 3, 243-257 (1997), July This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.