American Institute of Mathematical Sciences

July  2015, 11(3): 867-886. doi: 10.3934/jimo.2015.11.867

Performance analysis of backup-task scheduling with deadline time in cloud computing

 1 Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan 2 Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara 630-0192

Received  October 2013 Revised  May 2014 Published  October 2014

In large-scale parallel job processing for cloud computing, a huge task is divided into subtasks, which are processed independently on a cluster of machines called workers. Since the task processing lasts until all the subtasks are completed, a slow worker machine makes the overall task-processing time long, degrading the task-level throughput. In order to alleviate the performance degradation, MapReduce conducts backup execution, in which the master node schedules the remaining in-progress subtasks when the whole task operation is close to completion. In this paper, we investigate the effect of backup tasks on the task-level throughput. We consider the backup-task scheduling in which a backup subtask for a worker starts when the subtask-processing time of the worker reaches the deadline time. We analyze the task-level processing-time distribution by considering the maximum subtask-processing time among workers. The task throughput and the amount of all the workers' processing times are derived when the worker-processing-time (WPT) follows a hyper-exponential, Weibull, and Pareto distribution. We also propose an approximate method to derive performance measures based on extreme value theory. The approximations are validated by Monte Carlo simulation. Numerical examples show that the performance improvement by backup tasks significantly depends on workers' processing time distribution.
Citation: Kyosuke Hashimoto, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of backup-task scheduling with deadline time in cloud computing. Journal of Industrial & Management Optimization, 2015, 11 (3) : 867-886. doi: 10.3934/jimo.2015.11.867
References:
 [1] Journal of Parallel and Distributed Computing, 71 (2011), 556-564. doi: 10.1016/j.jpdc.2010.11.003.  Google Scholar [2] Morgan & Claypool, 2009. doi: 10.2200/S00193ED1V01Y200905CAC006.  Google Scholar [3] Parallel Computing, 33 (2007), 213-234. doi: 10.1016/j.parco.2007.01.002.  Google Scholar [4] Communications of the ACM, 51 (2008), 107-113. doi: 10.1145/1327452.1327492.  Google Scholar [5] IEEE Transactions on Parallel and Distributed Systems, 20 (2009), 207-218. doi: 10.1109/TPDS.2008.61.  Google Scholar [6] Springer, Berlin, 1997. doi: 10.1007/978-3-642-33483-2.  Google Scholar [7] Journal of Industrial and Management Optimization, 10 (2014), 113-129. doi: 10.3934/jimo.2014.10.113.  Google Scholar [8] 2nd edition, Cambridge University Press, 1992.  Google Scholar [9] Springer Series in Operations Research and Financial Engineering. Springer, New York, 2008.  Google Scholar [10] 2nd edition, O'reilly Media, California, 2008. Google Scholar [11] With a foreword by Aad van Moorsel. Springer, Heidelberg, 2010. doi: 10.1007/978-3-642-11257-7.  Google Scholar

show all references

References:
 [1] Journal of Parallel and Distributed Computing, 71 (2011), 556-564. doi: 10.1016/j.jpdc.2010.11.003.  Google Scholar [2] Morgan & Claypool, 2009. doi: 10.2200/S00193ED1V01Y200905CAC006.  Google Scholar [3] Parallel Computing, 33 (2007), 213-234. doi: 10.1016/j.parco.2007.01.002.  Google Scholar [4] Communications of the ACM, 51 (2008), 107-113. doi: 10.1145/1327452.1327492.  Google Scholar [5] IEEE Transactions on Parallel and Distributed Systems, 20 (2009), 207-218. doi: 10.1109/TPDS.2008.61.  Google Scholar [6] Springer, Berlin, 1997. doi: 10.1007/978-3-642-33483-2.  Google Scholar [7] Journal of Industrial and Management Optimization, 10 (2014), 113-129. doi: 10.3934/jimo.2014.10.113.  Google Scholar [8] 2nd edition, Cambridge University Press, 1992.  Google Scholar [9] Springer Series in Operations Research and Financial Engineering. Springer, New York, 2008.  Google Scholar [10] 2nd edition, O'reilly Media, California, 2008. Google Scholar [11] With a foreword by Aad van Moorsel. Springer, Heidelberg, 2010. doi: 10.1007/978-3-642-11257-7.  Google Scholar
 [1] Amru Hussein, Martin Saal, Marc Wrona. Primitive equations with horizontal viscosity: The initial value and The time-periodic problem for physical boundary conditions. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3063-3092. doi: 10.3934/dcds.2020398 [2] Beom-Seok Han, Kyeong-Hun Kim, Daehan Park. A weighted Sobolev space theory for the diffusion-wave equations with time-fractional derivatives on $C^{1}$ domains. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3415-3445. doi: 10.3934/dcds.2021002 [3] Takeshi Saito, Kazuyuki Yagasaki. Chebyshev spectral methods for computing center manifolds. Journal of Computational Dynamics, 2021  doi: 10.3934/jcd.2021008 [4] Christoforidou Amalia, Christian-Oliver Ewald. A lattice method for option evaluation with regime-switching asset correlation structure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1729-1752. doi: 10.3934/jimo.2020042 [5] Vieri Benci, Marco Cococcioni. The algorithmic numbers in non-archimedean numerical computing environments. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1673-1692. doi: 10.3934/dcdss.2020449 [6] Enkhbat Rentsen, N. Tungalag, J. Enkhbayar, O. Battogtokh, L. Enkhtuvshin. Application of survival theory in Mining industry. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 443-448. doi: 10.3934/naco.2020036 [7] Samira Shahsavari, Saeed Ketabchi. The proximal methods for solving absolute value equation. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 449-460. doi: 10.3934/naco.2020037 [8] Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311 [9] Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451 [10] Fioralba Cakoni, Shixu Meng, Jingni Xiao. A note on transmission eigenvalues in electromagnetic scattering theory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021025 [11] Lars Grüne, Luca Mechelli, Simon Pirkelmann, Stefan Volkwein. Performance estimates for economic model predictive control and their application in proper orthogonal decomposition-based implementations. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021013 [12] Saeed Assani, Muhammad Salman Mansoor, Faisal Asghar, Yongjun Li, Feng Yang. Efficiency, RTS, and marginal returns from salary on the performance of the NBA players: A parallel DEA network with shared inputs. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021053 [13] Muberra Allahverdi, Harun Aydilek, Asiye Aydilek, Ali Allahverdi. A better dominance relation and heuristics for Two-Machine No-Wait Flowshops with Maximum Lateness Performance Measure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1973-1991. doi: 10.3934/jimo.2020054 [14] M. Mahalingam, Parag Ravindran, U. Saravanan, K. R. Rajagopal. Two boundary value problems involving an inhomogeneous viscoelastic solid. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1351-1373. doi: 10.3934/dcdss.2017072 [15] Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151 [16] Oleksandr Boichuk, Victor Feruk. Boundary-value problems for weakly singular integral equations. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021094 [17] Hui Yang, Yuzhu Han. Initial boundary value problem for a strongly damped wave equation with a general nonlinearity. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021019 [18] W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349 [19] Qi Lü, Xu Zhang. A concise introduction to control theory for stochastic partial differential equations. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021020 [20] Florian Dorsch, Hermann Schulz-Baldes. Random Möbius dynamics on the unit disc and perturbation theory for Lyapunov exponents. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021076

2019 Impact Factor: 1.366

Metrics

• PDF downloads (73)
• HTML views (0)
• Cited by (2)

Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]