Performance analysis of large-scale parallel-distributed  processing with backup tasks for cloud computing

Tsuguhito Hirai; Hiroyuki Masuyama; Shoji Kasahara; Yutaka Takahashi

doi:10.3934/jimo.2014.10.113

Article Contents

2014, Volume 10, Issue 1: 113-129. Doi: 10.3934/jimo.2014.10.113

This issue Previous Article Analysis of an M/M/1 queueing system with impatient customers and a variant of multiple vacation policy Next Article The impact of the $NT$-policy on the behaviour of a discrete-time queue with general service times

Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing

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

Received: September 2012

Revised: June 2013

Published: January 2014

Abstract / Introduction Related Papers Cited by

Abstract

In cloud computing, a large-scale parallel-distributed processing service is provided where a huge task is split into a number of subtasks and those subtasks are processed on a cluster of machines called workers. In such a processing service, a worker which takes a long time for processing a subtask makes the response time long (the issue of stragglers). One of efficient methods to alleviate this issue is to execute the same subtask by another worker in preparation for the slow worker (backup tasks). In this paper, we consider the efficiency of backup tasks. We model the task-scheduling server as a single-server queue, in which the server consists of a number of workers. When a task enters the server, the task is split into subtasks, and each subtask is served by its own worker and an alternative distinct worker. In this processing, we explicitly derive task processing time distributions for the two cases that the subtask processing time of a worker obeys Weibull or Pareto distribution. We compare the mean response time and the total processing time under backup-task scheduling with those under normal scheduling. Numerical examples show that the efficiency of backup-task scheduling significantly depends on workers' processing time distribution.

Keywords:

Mathematics Subject Classification: Primary: 60K25, 60J10; Secondary: 68M20.

Citation:

Related Papers

Cited by

References

[1]	M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica and M. Zaharia, A view of cloud computing, Communications of the ACM, 53 (2010), 50-58.doi: 10.1145/1721654.1721672.
[2]	L. A. Barroso and U. Hölzle, "The Datacenter as A Computer: An Introduction to the Design of Warehouse-Scale Machines," Morgan & Claypool, California, 2009.doi: 10.2200/S00193ED1V01Y200905CAC006.
[3]	W. Cirne, D. Paranhos, F. Brasileiro and L. F. W. Góes, On the efficacy, efficiency and emergent behavior of task replication in large distributed systems, Parallel Computing, 33 (2007), 213-234.doi: 10.1016/j.parco.2007.01.002.
[4]	J. Dean and S. Ghemawat, MapReduce: Simplified data processing on large clusters, Communications of the ACM, 51 (2008), 107-113.doi: 10.1145/1327452.1327492.
[5]	J. Dejun, G. Pierre and C.-H. Chi, EC2 performance analysis for resource provisioning of service-oriented applications, Proc. Service-Oriented Computing: ICSOC/ServiceWave 2009 Workshops, Lecture Notes in Computer Science, 6275 (2010), 197-207.doi: 10.1007/978-3-642-16132-2_19.
[6]	M. Dobber, R. V. D. Mei and G. Koole, Dynamic load balancing and job replication in a global-scale grid environment: A comparison, IEEE Transactions on Parallel and Distributed Systems, 20 (2009), 207-218.doi: 10.1109/TPDS.2008.61.
[7]	D. Gross, J. F. Shortle, J. M. Thompson and C. M. Harris, "Fundamentals of Queueing Theory," $4^{th}$ edition, John Wiley & Sons, New Jersey, 2008.doi: 10.1002/9781118625651.
[8]	K. Xiong and H. Perros, Service performance and analysis in cloud computing, Proc. 2009 IEEE Congress on Services Services - I, (2009), 693-700.doi: 10.1109/SERVICES-I.2009.121.
[9]	N. Yigitbasi, A. Iosup, D. Epema and S. Ostermann, C-Meter: A framework for performance analysis of computing clouds, Proc. 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, (2009), 472-477.doi: 10.1109/CCGRID.2009.40.