
Previous Article
Optimal liability ratio and dividend payment strategies under catastrophic risk
 JIMO Home
 This Issue

Next Article
Compensation plan, pricing and production decisions with inventorydependent salvage value, and asymmetric riskaverse sales agent
Performance optimization of paralleldistributed processing with checkpointing for cloud environment
1.  Graduate School of Informatics, Kyoto University, YoshidaHommachi, Sakyoku, Kyoto 6068501, Japan 
2.  Graduate School of Information Science, Nara Institute of Science and Technology, 89165 Takayama, Ikoma, Nara 6300192, Japan 
In cloud computing, the most successful application framework is paralleldistributed processing, in which an enormous task is split into a number of subtasks and those are processed independently on a cluster of machines referred to as workers. Due to its huge system scale, worker failures occur frequently in cloud environment and failed subtasks cause a large processing delay of the task. One of schemes to alleviate the impact of failures is checkpointing method, with which the progress of a subtask is recorded as checkpoint and the failed subtask is resumed by other worker from the latest checkpoint. This method can reduce the processing delay of the task. However, frequent checkpointing is system overhead and hence the checkpoint interval must be set properly. In this paper, we consider the optimal number of checkpoints which minimizes the taskprocessing time. We construct a stochastic model of paralleldistributed processing with checkpointing and approximately derive explicit expressions for the mean taskprocessing time and the optimal number of checkpoints. Numerical experiments reveal that the proposed approximations are sufficiently accurate on typical environment of cloud computing. Furthermore, the derived optimal number of checkpoints outperforms the result of previous study for minimizing the taskprocessing time on paralleldistributed processing.
References:
[1] 
L. A. Barroso and U. Hölzle, The Datacenter as a Computer: An Introduction to the Design of WarehouseScale Machines, Morgan & Claypool Publishers, California, 2009. doi: 10.2200/S00193ED1V01Y200905CAC006. Google Scholar 
[2] 
T. C. Bressoud and M. A. Kozuch, Cluster faulttolerance: An experimental evaluation of checkpointing and MapReduce through simulation in Proc. the IEEE International Conference on Cluster Computing and Workshops (CLUSTER 2009), (2009). doi: 10.1109/CLUSTR.2009.5289185. Google Scholar 
[3] 
C. L. P. Chen and C.Y. Zhang, Dataintensive applications, challenges, techniques and technologies: A survey on big data, Information Sciences, 275 (2014), 314347. doi: 10.1016/j.ins.2014.01.015. Google Scholar 
[4] 
T. Condie, N. Conway, P. Alvaro, J. M. Hellerstein, K. Elmeleegy and R. Sears, MapReduce online, in Proc. the 7th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2010), (2010). Google Scholar 
[5] 
J. T. Daly, A higher order estimate of the optimum checkpoint interval for restart dumps, Future Generation Computer Systems, 22 (2006), 303312. doi: 10.1016/j.future.2004.11.016. Google Scholar 
[6] 
J. Dean and S. Ghemawat, MapReduce: Simplified data processing on large clusters, Communications of the ACM, 51 (2008), 107113. doi: 10.1145/1327452.1327492. Google Scholar 
[7] 
J. Dean, Designs, lessons and advice from building large distributed systems, in Keynote Presentation of the 3rd ACM SIGOPS International Workshop on Large Scale Distributed Systems and Middleware (LADIS 2009), (2009). Google Scholar 
[8] 
J. Dean and S. Ghemawat, MapReduce: A flexible data processing tool, Communications of the ACM, 53 (2010), 7277. doi: 10.1145/1629175.1629198. Google Scholar 
[9] 
S. Di, Y. Robert, F. Vivien, D. Kondo, C. L. Wang and F. Cappello, Optimization of cloud task processing with checkpointrestart mechanism in Proc. the International Conference for High Performance Computing, Networking, Storage and Analysis (SC 13), (2013). doi: 10.1145/2503210.2503217. Google Scholar 
[10] 
L. Fialho, D. Rexachs and E. Luque, What is missing in current checkpoint interval models?, Proc. the 31st International Conference on Distributed Computing Systems (ICDCS 2011), (2011), 322332. doi: 10.1109/ICDCS.2011.12. Google Scholar 
[11] 
B. Javadi, D. Kondo, A. Iosup and D. Epema, The failure trace archive: Enabling the comparison of failure measurements and models of distributed systems, Journal of Parallel and Distributed Computing, 73 (2013), 12081223. doi: 10.1016/j.jpdc.2013.04.002. Google Scholar 
[12] 
H. Jin, Y. Chen, H. Zhu and X.H. Sun, Optimizing HPC faulttolerant environment: An analytical approach, Proc. the 39th International Conference on Parallel Processing (ICPP 2010), (2010), 525534. doi: 10.1109/ICPP.2010.80. Google Scholar 
[13] 
A. Martin, T. Knauth, S. Creutz, D. Becker, S. Weigert, C. Fetzer and A. Brito, Lowoverhead fault tolerance for highthroughput data processing systems, Proc. the 31st International Conference on Distributed Computing Systems (ICDCS 2011), (2011), 689699. doi: 10.1109/ICDCS.2011.29. Google Scholar 
[14] 
P. Mell and T. Grance, The NIST Definition of Cloud Computing, Recommendations of the National Institute of Standards and Technology, NIST Special Publication 800145,2011. doi: 10.6028/NIST.SP.800145. Google Scholar 
[15] 
M. Taifi, J. Y. Shi and A. Khreishah, SpotMPI: A framework for auctionbased HPC computing using Amazon spot instances, Proc. the 11th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2011), (2011), 109120. doi: 10.1007/9783642246692_11. Google Scholar 
[16] 
J. W. Young, A first order approximation to the optimum checkpoint interval, Communications of the ACM, 17 (1974), 530531. doi: 10.1145/361147.361115. Google Scholar 
[17] 
M. Zaharia, T. Das, H. Li, T. Hunter, S. Shenker and I. Stoica, Discretized streams: Faulttolerant streaming computation at scale, Proc. the 24th ACM Symposium on Operating Systems Principles (SOSP 2013), (2013), 423438. doi: 10.1145/2517349.2522737. Google Scholar 
show all references
References:
[1] 
L. A. Barroso and U. Hölzle, The Datacenter as a Computer: An Introduction to the Design of WarehouseScale Machines, Morgan & Claypool Publishers, California, 2009. doi: 10.2200/S00193ED1V01Y200905CAC006. Google Scholar 
[2] 
T. C. Bressoud and M. A. Kozuch, Cluster faulttolerance: An experimental evaluation of checkpointing and MapReduce through simulation in Proc. the IEEE International Conference on Cluster Computing and Workshops (CLUSTER 2009), (2009). doi: 10.1109/CLUSTR.2009.5289185. Google Scholar 
[3] 
C. L. P. Chen and C.Y. Zhang, Dataintensive applications, challenges, techniques and technologies: A survey on big data, Information Sciences, 275 (2014), 314347. doi: 10.1016/j.ins.2014.01.015. Google Scholar 
[4] 
T. Condie, N. Conway, P. Alvaro, J. M. Hellerstein, K. Elmeleegy and R. Sears, MapReduce online, in Proc. the 7th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2010), (2010). Google Scholar 
[5] 
J. T. Daly, A higher order estimate of the optimum checkpoint interval for restart dumps, Future Generation Computer Systems, 22 (2006), 303312. doi: 10.1016/j.future.2004.11.016. Google Scholar 
[6] 
J. Dean and S. Ghemawat, MapReduce: Simplified data processing on large clusters, Communications of the ACM, 51 (2008), 107113. doi: 10.1145/1327452.1327492. Google Scholar 
[7] 
J. Dean, Designs, lessons and advice from building large distributed systems, in Keynote Presentation of the 3rd ACM SIGOPS International Workshop on Large Scale Distributed Systems and Middleware (LADIS 2009), (2009). Google Scholar 
[8] 
J. Dean and S. Ghemawat, MapReduce: A flexible data processing tool, Communications of the ACM, 53 (2010), 7277. doi: 10.1145/1629175.1629198. Google Scholar 
[9] 
S. Di, Y. Robert, F. Vivien, D. Kondo, C. L. Wang and F. Cappello, Optimization of cloud task processing with checkpointrestart mechanism in Proc. the International Conference for High Performance Computing, Networking, Storage and Analysis (SC 13), (2013). doi: 10.1145/2503210.2503217. Google Scholar 
[10] 
L. Fialho, D. Rexachs and E. Luque, What is missing in current checkpoint interval models?, Proc. the 31st International Conference on Distributed Computing Systems (ICDCS 2011), (2011), 322332. doi: 10.1109/ICDCS.2011.12. Google Scholar 
[11] 
B. Javadi, D. Kondo, A. Iosup and D. Epema, The failure trace archive: Enabling the comparison of failure measurements and models of distributed systems, Journal of Parallel and Distributed Computing, 73 (2013), 12081223. doi: 10.1016/j.jpdc.2013.04.002. Google Scholar 
[12] 
H. Jin, Y. Chen, H. Zhu and X.H. Sun, Optimizing HPC faulttolerant environment: An analytical approach, Proc. the 39th International Conference on Parallel Processing (ICPP 2010), (2010), 525534. doi: 10.1109/ICPP.2010.80. Google Scholar 
[13] 
A. Martin, T. Knauth, S. Creutz, D. Becker, S. Weigert, C. Fetzer and A. Brito, Lowoverhead fault tolerance for highthroughput data processing systems, Proc. the 31st International Conference on Distributed Computing Systems (ICDCS 2011), (2011), 689699. doi: 10.1109/ICDCS.2011.29. Google Scholar 
[14] 
P. Mell and T. Grance, The NIST Definition of Cloud Computing, Recommendations of the National Institute of Standards and Technology, NIST Special Publication 800145,2011. doi: 10.6028/NIST.SP.800145. Google Scholar 
[15] 
M. Taifi, J. Y. Shi and A. Khreishah, SpotMPI: A framework for auctionbased HPC computing using Amazon spot instances, Proc. the 11th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2011), (2011), 109120. doi: 10.1007/9783642246692_11. Google Scholar 
[16] 
J. W. Young, A first order approximation to the optimum checkpoint interval, Communications of the ACM, 17 (1974), 530531. doi: 10.1145/361147.361115. Google Scholar 
[17] 
M. Zaharia, T. Das, H. Li, T. Hunter, S. Shenker and I. Stoica, Discretized streams: Faulttolerant streaming computation at scale, Proc. the 24th ACM Symposium on Operating Systems Principles (SOSP 2013), (2013), 423438. doi: 10.1145/2517349.2522737. Google Scholar 
Parameter  Description  Value 
Number of workers  
Subtaskprocessing time  
Time to make a checkpoint  
Mean time between worker failures  
Time to resume a failed subtask  
Number of checkpoints 
Parameter  Description  Value 
Number of workers  
Subtaskprocessing time  
Time to make a checkpoint  
Mean time between worker failures  
Time to resume a failed subtask  
Number of checkpoints 
[1] 
KarlPeter Hadeler, Frithjof Lutscher. Quiescent phases with distributed exit times. Discrete & Continuous Dynamical Systems  B, 2012, 17 (3) : 849869. doi: 10.3934/dcdsb.2012.17.849 
[2] 
Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems  B, 2016, 21 (6) : 16711687. doi: 10.3934/dcdsb.2016017 
[3] 
Jan Prüss, Laurent PujoMenjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems  B, 2006, 6 (1) : 225235. doi: 10.3934/dcdsb.2006.6.225 
[4] 
Raz Kupferman, Cy Maor. The emergence of torsion in the continuum limit of distributed edgedislocations. Journal of Geometric Mechanics, 2015, 7 (3) : 361387. doi: 10.3934/jgm.2015.7.361 
[5] 
Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327345. doi: 10.3934/naco.2013.3.327 
[6] 
Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021004 
[7] 
Xiaomao Deng, XiaoChuan Cai, Jun Zou. A parallel spacetime domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 10691091. doi: 10.3934/ipi.2015.9.1069 
[8] 
Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of CuckerSmale type. Kinetic & Related Models, 2011, 4 (1) : 116. doi: 10.3934/krm.2011.4.1 
[9] 
Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367376. doi: 10.3934/proc.2009.2009.367 
[10] 
SeungYeal Ha, Shi Jin. Local sensitivity analysis for the CuckerSmale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859889. doi: 10.3934/krm.2018034 
[11] 
Carlos FresnedaPortillo, Sergey E. Mikhailov. Analysis of BoundaryDomain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 30593088. doi: 10.3934/cpaa.2019137 
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]