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 singleserver 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 backuptask scheduling with those under normal scheduling. Numerical examples show that the efficiency of backup-task scheduling significantly depends on workers' processing time distribution. 2010 Mathematics Subject Classification. Primary: 60K25, 60J10; Secondary: 68M20. Key words and phrases. Cloud computing, Parallel-distributed processing, Task scheduling, Backup tasks, Queueing analysis. The reviewing process of the paper was handled by Wuyi Yue as Guest Editor. This is a pre-copy-editing, author-produced PDF of an article accepted for publication in Journal of Industrial and Management Optimization following peer review. The definitive publisherauthenticated version, T. Hirai, H. Masuyama, S. Kasahara and Y. Takahashi, "Performance Analysis of Large-Scale Parallel-Distributed Processing with Backup Tasks for Cloud Computing," Journal of Industrial and Management Optimization, vol. 10, no. 1, pp. 113-129, 2014, is available online at doi:10.3934/jimo.2014.10.113. 1. Introduction. Recently, cloud computing has attracted considerable attention due to the availability of huge computing resources and its significant cost efficiency. In [1], cloud computing is defined as the sum of the existing concepts, software as a service (SaaS) and utility computing. More precisely, cloud computing is the combined concept of providing computer-processing service only as needed via the Internet (SaaS) and using server resources in a data center only as needed (utility computing). A remarkable feature of cloud computing is that data centers providing cloud computing services are extremely large-sized. With the increase in the capacity of hard-disk drives, the amount of data treated in computer processing also increases, and it is common that enormous time is needed in data processing with one worker machine. In cloud computing, enormous data is handled with a huge number of workers in parallel-distributed processing fashion [4, 2] , and typical applications are data mining, document processing, and machine learning. In the following, we call this processing mechanism as a largescale parallel-distributed processing. With a large-scale parallel-distributed processing, huge data is processed in relatively short time. Roughly speaking, data processing which needs 100 hours with one worker can process in one hour with 100 workers if overhead for parallel processing is relatively small. In the large-scale parallel-distributed processing, a huge task is split into a number of subtasks and those subtasks are independently processed on a cluster of machines called workers. The huge task processing ends when all the subtasks are completed. Therefore, a worker machine which takes a long time for processing a subtask increases the response time (the issue of stragglers) [4] . The reasons causing slow workers are machine failure and resource competition because the system consists of a huge number of machines. In order to alleviate the issue of stragglers, there exist two scheduling schemes: load balancing [6] and backup tasks [4] . In load balancing, the subtask size for a worker is determined according to the processing speed of the worker. That is, a small-sized subtask is allocated to a slow-processing worker, while a largesized subtask is performed by a fast-processing worker. This scheduling makes the variance of the subtask-processing times of worker machines significantly small. However, the load-balancing scheduler must know each worker's subtask-processing time a priori. In backup-task scheduling, on the other hand, backup executions of the remaining in-progress subtasks are scheduled. Then the process of a subtask ends when either original subtask or backup executions is completed. A strong point of the backuptask scheduling is that the backup-task scheduler activates backup tasks for a worker according to the elapsed subtask-processing time, i.e., no a priori information about the overall subtask-proceeding time of the worker is needed. It is reported in [4] that the backup tasks can significantly reduce the response time of a task. There is much literature on cloud computing, and most of works are concerned with service platform and cost efficiency from the economical point of view. There are a few studies for performance issues on cloud computing, and those are based on measurement-based analysis. (See, for example, [5, 9] .) In terms of the theoretical approach to performance issues on cloud computing, Xiong et al. [8] consider a queueing network model which consists of a Web-server queue and a service-center queue. Focusing on the percentile of the response time as a performance measure of cloud computing, they approximately analyze the response time distribution. In their model, however, the service-center part is modeled as a single-server queue
In REF , Tsuguhito Hirai et al. have taken the efficiency of backup tasks into consideration.
Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing
Journal of Industrial and Management Optimization
Computer Science