Cooperative checkpointing: a robust approach to large-scale systems reliability

ABSTRACT

Cooperative checkpointing increases the performance and robustness of a system by allowing checkpoints requested by applications to be dynamically skipped at runtime. A robust system must be more than merely resilient to failures; it must be adaptable and flexible in the face of new and evolving challenges. A simulation-based experimental analysis using both probabilistic and harvested failure distributions reveals that cooperative checkpointing enables an application to make progress under a wide variety of failure distributions that periodic checkpointing lacks the flexibility to handle. Cooperative checkpointing can be easily implemented on top of existing application-initiated checkpointing mechanisms and may be used to enhance other reliability techniques like QoS guarantees and fault-aware job scheduling. The simulations also support a number of theoretical predictions related to cooperative checkpointing, including the non-competitiveness of periodic checkpointing.

REFERENCES

• 1: N. Adiga and T. B. Team. An overview of the bluegene/l supercomputer. In Supercomputing, Technical Papers, Nov. 2002.
• 2: Saurabh Agarwal , Rahul Garg , Meeta S. Gupta , Jose E. Moreira, Adaptive incremental checkpointing for massively parallel systems, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006248]
• 3: Sung-Eun Choi , Steven J. Deitz, Compiler Support for Automatic Checkpointing, Proceedings of the 16th Annual International Symposium on High Performance Computing Systems and Applications, p.213, June 16-19, 2002
• 4: Thomas G. Dietterich , Ryszard S. Michalski, Discovering patterns in sequences of events, Artificial Intelligence, v.25 n.2, p.187-232, Feb. 1985 [doi>10.1016/0004-3702(85)90003-7]
• 5: E. N. Elnozahy, D. B. Johnson, and W. Zwaenepoel. The performance of consistent checkpointing. In 11th Symposium on Reliable Distributed Systems, Houston, TX, Oct. 1992.
• 6: Elmootazbellah N. Elnozahy , James S. Plank, Checkpointing for Peta-Scale Systems: A Look into the Future of Practical Rollback-Recovery, IEEE Transactions on Dependable and Secure Computing, v.1 n.2, p.97-108, April 2004 [doi>10.1109/TDSC.2004.15]
• 7: D. G. Feitelson. Parallel workloads archive. URL: http://cs.huji.ac.il/labs/parallel/workload/, 2001.
• 8: R. K. Jain. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. Wiley-Interscience, New York, 1991.
• 9: I. Lee, R. K. Iyer, and D. Tang. Error/failure analysis using event logs from fault tolerant systems. In Proceedings of the 21st Intl. Symposium on Fault-Tolerant Computing, pages 10--17, June 1991.
• 10: Yinglung Liang , Yanyong Zhang , Anand Sivasubramaniam , Morris Jette , Ramendra Sahoo, BlueGene/L Failure Analysis and Prediction Models, Proceedings of the International Conference on Dependable Systems and Networks (DSN'06), p.425-434, June 25-28, 2006 [doi>10.1109/DSN.2006.18]
• 11: Yinglung Liang , Anand Sivasubramaniam , Jose Moreira, Filtering Failure Logs for a BlueGene/L Prototype, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.476-485, June 28-July 01, 2005 [doi>10.1109/DSN.2005.50]
• 12: Alison N. Norman , Sung-Eun Choi , Calvin Lin, Compiler-generated staggered checkpointing, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-8, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066663]
• 13: A. J. Oliner. Cooperative checkpointing for supercomputing systems. Master's thesis, Massachusetts Institute of Technology, 2005.
• 14: A. J. Oliner, L. Rudolph, and R. K. Sahoo. Cooperative checkpointing theory. In Proceedings of IPDPS, Intl. Parallel and Distributed Processing Symposium, 2006.
• 15: A. J. Oliner , J. E. Moreira, Probabilistic QoS Guarantees for Supercomputing Systems, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.634-643, June 28-July 01, 2005 [doi>10.1109/DSN.2005.80]
• 16: A. J. Oliner and R. K. Sahoo. Evaluating cooperative checkpointing for supercomputing systems. In IEEE IPDPS, Workshop on System Management Tools for Large-scale Parallel Systems, Apr. 2006.
• 17: A. J. Oliner, R. K. Sahoo, J. E. Moreira, and M. Gupta. Performance implications of periodic checkpointing on large-scale cluster systems. In IEEE IPDPS, Workshop on System Management Tools for Large-scale Parallel Systems, Apr. 2005.
• 18: J. S. Plank , W. R. Elwasif, Experimental Assessment of Workstation Failures and Their Impact on Checkpointing Systems, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.48, June 23-25, 1998
• 19: James S. Plank , Michael G. Thomason, Processor allocation and checkpoint interval selection in cluster computing systems, Journal of Parallel and Distributed Computing, v.61 n.11, p.1570-1590, November 2001 [doi>10.1006/jpdc.2001.1757]
• 20: R. K. Sahoo , A. J. Oliner , I. Rish , M. Gupta , J. E. Moreira , S. Ma , R. Vilalta , A. Sivasubramaniam, Critical event prediction for proactive management in large-scale computer clusters, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956799]
• 21: Martin Schulz , Greg Bronevetsky , Rohit Fernandes , Daniel Marques , Keshav Pingali , Paul Stodghill, Implementation and Evaluation of a Scalable Application-Level Checkpoint-Recovery Scheme for MPI Programs, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.38, November 06-12, 2004 [doi>10.1109/SC.2004.29]
• 22: Asser N. Tantawi , Manfred Ruschitzka, Performance analysis of checkpointing strategies, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.123-144, May 1984 [doi>10.1145/190.357398]
• 23: John W. Young, A first order approximation to the optimum checkpoint interval, Communications of the ACM, v.17 n.9, p.530-531, Sept. 1974 [doi>10.1145/361147.361115]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Experimentation, Measurement, Reliability

Keywords:
RAS, cooperative checkpointing, high-performance computing, parallel computing, simulations, supercomputing