Checkpointing is a technique to back up work at periodic intervals so that if computation fails, it will not be necessary to restart from the beginning but will instead be able to restart from the latest checkpoint. Performing checkpointing operations requires time. Therefore, it is necessary to consider the tradeoff between the time to perform checkpointing operations and the time saved when computation restarts at a checkpoint. This article presents a method to model the impact of correlated failures on an application that performs a specified amount of computation and implements checkpointing operations at equidistant periods during this computation. We develop a Markov model and superimpose a correlated life distribution. Two cases are considered. The first assumes that reaching a checkpoint resets the failure distribution. The second allows the probability of failure to progress. We illustrate the approach through a series of examples. The results indicate that correlation can negatively impact checkpointing, necessitating more frequent checkpointing and increasing the total time required, but that the approach can still identify the optimal number of equidistant checkpoints, despite this correlation.
Di MartinoCKalbarczykZIyerR. Measuring the resiliency of extreme-scale computing environments. In: FiondellaLPuliafitoA (eds) Principles of performance and reliability modeling and evaluation: essays in honor of Kishor Trivedi on his 70th birthday (Springer Series in Reliability Engineering). Cham: Springer, 2016, pp.118–129.
2.
RandellBLeePTreleavenP.Reliability issues in computing system design. ACM Comput Surv1978; 10(2): 123–165.
KooRTouegS.Checkpointing and rollback-recovery for distributed systems. IEEE Trans Softw Eng1987; 1: 23–31.
5.
DohiTNaotoKTrivediK.Availability models with age-dependent checkpointing. In: Proceedings of the IEEE 21st symposium on reliable distributed systems, Suita, Japan, 13–16 October 2002, pp.130–139. New York: IEEE.
6.
WolterK.Stochastic models for fault tolerance: restart, rejuvenation and checkpointing. Berlin: Springer, 2010.
7.
L’EcuyerPMalenfantJ.Computing optimal checkpointing strategies for rollback and recovery systems. IEEE Trans Comput1988; 37(4): 491–496.
8.
DeconinckGVounckxJLauwereinsR, et al. Survey of backward error recovery techniques for multicomputers based on checkpointing and rollback. Int J Model Simul1998; 18(1): 66–71.
9.
KalaiselviSRajaramanV.A survey of checkpointing algorithms for parallel and distributed computers. Sadhana2000; 25(5): 489–510.
10.
EgwutuohaILevyDSelicB, et al. A survey of fault tolerance mechanisms and checkpoint/restart implementations for high performance computing systems. J Supercomput2013; 65(3): 1302–1326.
11.
ShahzadFWittmannMKreutzerM, et al. A survey of checkpoint/restart techniques on distributed memory systems. Parall Process Lett2013; 23(4): 1340011.
12.
GelenbeE.On the optimum checkpoint interval. J ACM1979; 26(2): 259–270.
13.
AuricheLQuagliaFCicianiB.Run-time selection of the checkpoint interval in time warp based simulations. Simul Pract Theory1998; 6(5): 461–478.
14.
KwakSWooBByungK.An optimal checkpointing-strategy for real-time control systems under transient faults. IEEE Trans Reliab2001; 50(3): 293–301.
15.
GuptaRHarishNPeteB.Understanding checkpointing overheads on massive-scale systems: analysis of the IBM Blue Gene/P system. Int J High Perform Comput Appl2011; 25(2): 180–192.
16.
BougeretMCasanovaHRabieM, et al. Checkpointing strategies for parallel jobs. In: Proceedings of the ACM international conference for high performance computing, networking, storage and analysis, 2011, https://core.ac.uk/download/pdf/52314073.pdf
17.
LevitinGXingLDaiY.Preventive replacements in real-time standby systems with periodic backups. IEEE Trans Reliab2017; 66(3): 771–782.
18.
LevitinGXingLZhaiQ, et al. Optimization of full versus incremental periodic backup policy. IEEE Trans Depend Sec Comput2016; 13(6): 644–656.
19.
BenoitASaurabhRRobertY.Efficient checkpoint/verification patterns. Int J High Perform Comput Appl2017; 31(1): 52–65.
20.
HuangYKintalaCKolettisN, et al. Software rejuvenation: analysis, module and applications. In: Proceedings of the IEEE 25th international symposium on fault-tolerant computing, Pasadena, CA, 27–30 June 1995, pp.381–390. New York: IEEE.
21.
GargSHuangYKintalaC, et al. Minimizing completion time of a program by checkpointing and rejuvenation. ACM SIGMETRICS Perform Eval Rev1996; 24(1): 252–261.
22.
BobbioAGargSGribaudoM, et al. Modeling software systems with rejuvenation, restoration and checkpointing through fluid stochastic Petri nets. In: Proceedings of the IEEE 8th international workshop on Petri nets and performance models, Zaragoza, 8–10September1999, pp.82–91. New York: IEEE.
23.
OkamuraHDohiT.Comprehensive evaluation of aperiodic checkpointing and rejuvenation schemes in operational software system. J Syst Softw2010; 83(9): 1591–1604.
24.
NicolaVVan SpanjeJ.Comparative analysis of different models of checkpointing and recovery. IEEE Trans Softw Eng1990; 16(8): 807–821.
25.
TangDIyerR.Analysis and modeling of correlated failures in multicomputer systems. IEEE Trans Comput1992; 41(5): 567–577.
26.
BaldoniRHélaryJMostefaouiA, et al. A communication-induced checkpointing protocol that ensures rollback-dependency trackability. In: Proceedings of the IEEE 27th international symposium on fault-tolerant computing, Seattle, WA, 24–27 June 1997, pp.68–77. New York: IEEE.
27.
WangLPattabiramanKKalbarczykZ, et al. Modeling coordinated checkpointing for large-scale supercomputers. In: Proceedings of the IEEE international conference on dependable systems and networks, Yokohama, Japan, 28 June–1July 2005, pp.812–821. New York: IEEE.
28.
DiSBouguerraMBautista-GomezL, et al. Optimization of multi-level checkpoint model for large scale HPC applications. In: Proceedings of the IEEE 28th international parallel and distributed processing symposium, Phoenix, AZ, 19–23 May 2014, pp.1181–1190. New York: IEEE.
29.
TrivediK.Probability and statistics with reliability, queuing and computer science applications. Hoboken, NJ: John Wiley & Sons, 2008.
30.
StewartW.Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. Princeton, NJ: Princeton University Press, 2009.
31.
FiondellaLZeephongsekulP. Reliability of systems with identically distributed correlated components. In: Proceedings of the ISSAT 17th international conference on reliability and quality in design, Vancouver, BC, Canada, 4–6 August 2011, pp.26–30. Edison, NJ: ISSAT.
32.
BarlowRProschanF.Statistical theory of reliability and life testing: probability models. Tallahassee, FL: Florida State University, 1975.
33.
JafaryBFiondellaL.A universal generating function-based multi-state system performance model subject to correlated failures. Reliab Eng Syst Safe2016; 152: 16–27.
34.
LaiCXieM.Stochastic ageing and dependence for reliability. Berlin: Springer, 2006.
35.
ParkCParkTShinD. A simple method for generating correlated binary variates. Amer Statist1996; 50(4): 306–310.
