Fault-tolerant Scheduling for Differentiated Classes of Tasks with Low Replication Cost in Computational Grids Qin Zheng Depar tment of Electrical and Computer Engineering, National University of Singapore Bharadwaj Veeravalli Depar tment of Electrical and Computer Engineering, National University of Singapore Chen-Khong Tham Depar tment of Electrical and Computer Engineering, National University of Singapore eleqz@nus.edu.sg ABSTRACT elebv@nus.edu.sg eletck@nus.edu.sg Fault-tolerant scheduling is an imp erative step for largescale computational Grid systems, as often geographically distributed nodes co-op erate to execute a task. By and large, the primary-backup approach is a common methodology used for fault tolerance wherein each task has a primary copy and a backup copy on two different processors. Backup overloading has b een prop osed to reduce replication cost by allowing the backup copy to overload with other backup copies on the same processor. In this pap er, we consider two classes of indep endent tasks wherein b oth the classes have fault-tolerance requirements. Furthermore, Class 1 tasks require the resp onse time to b e as short as p ossible when a fault occurs, while Class 2 tasks prefer backups with minimum replication cost. We prop ose two algorithms, called the MRC-ECT algorithm and the MCT-LRC algorithm. Algorithm MRC-ECT is shown to guarantee an optimal backup schedule in terms of replication cost, while MCT-LRC can schedule a backup with minimum completion time and low replication cost. We conduct extensive simulation exp eriments to quantify the p erformance of the prop osed algorithms. Categories and Subject Descriptors C.2.4 [Computer-Communication Networks]: Distributed Systems--client/server, distributed applications disp ersed heterogeneous resources for solving various kinds of large-scale parallel applications in science, engineering and commerce [1]. These applications may b e submitted by Grid users dynamically via Grid middleware and may have tight deadline requirements. Running applications in such environments is susceptible to a wide range of failures as revealed by a recent survey [2] with real users on fault treatments in the Grid. In this pap er, we consider two classes of tasks that b oth require fault tolerance, but have differentiated QoS requirements in terms of resp onse time and cost. Tasks in the first class have strict resp onse time requirement even when failure occurs. Time critical grid applications such as simulations for medical surgery or disaster recovery b elong to this class. Tasks in the second class require low cost for fault tolerance. Provision of QoSaware Grid services without fault tolerance has b een studied in the Vienna Grid Environment by providing supp ort for dynamic negotiation of various QoS guarantees like required execution time and price [3]. As Grids are much more complex and heterogeneous than traditional computing systems, in a grid, one can discover a failure in a grid processor ab out what he/she could never know its hardware platform model has existed [2]. This pap er considers the problem of fault-tolerant scheduling of indep endent tasks arriving dynamically with deadline requirements in computational Grid, against processor failures1 . General Terms Algorithms 2. PROPOSED FAULT-TOLERANT SCHEDULING ALGORITHM The Grid system considered has M heterogeneous processors. Each indep endent task has three attributes: arrival time ta , deadline td , and execution time texe . The execution time of a task on processors is heterogeneous and we use te to denote its execution time on a processor Pe . Each task has a primary and a backup. The execution time of the primary and the backup could b e different dep ending on the processors that they are scheduled on. Resp onse time of a task is defined as the amount of time from its arrival to its completion. In failure-free situations, this time dep ends on the completion time of the primary. When failure happ ens, this time dep ends on the completion time of the backup. Let tB,c denote the completion time e of the backup if it is scheduled on processor Pe . Backup 1 Details on related works, the prop osed algorithms, proof of Lemmas, and simulation parameters and results can b e found in [5]. Keywords Computational Grids, scheduling, fault tolerance, differentiated tasks, resp onse time, replication cost 1. INTRODUCTION Grid computing has emerged as the next-generation parallel and distributed computing methodology that aggregates This work was supp orted in part by the Grid Computing pro ject (NUS WBS No: R-263-000-350-592) funded by SERC (through National Grid Office), ASTAR, Singap ore. Copyright is held by the author/owner(s). HPDC'07, June 25­29, 2007, Monterey, California, USA. ACM 978-1-59593-673-8/07/0006. 239 response time of a task on Pe is defined as: tB,res e = t B ,c e - ta (1) The significance of this lemma is as follows. It proves that to minimize backup replication cost, it is sufficient to consider only b oundary schedules. Replication cost is defined as the actual p ercentage of time need to b e scheduled for the backup b esides all overloaded p eriods. Let tO denote the amount of time that the backup e can overload with other backups on processor Pe . Replication cost to schedule the backup on Pe is defined as: cB,rep = e te - tO e te (2) 3. PERFORMANCE STUDY The results for two classes of tasks where MCT-LRC and MRC-ECT are used to schedule Class 1 and Class 2 tasks, resp ectively, are shown in Fig 2. We observe that b oth Class 1 and Class 2 tasks have similar p erformance in terms of rejection ratio and primary resp onse time. While Class 1 tasks have less backup resp onse time, Class 2 tasks have much lower replication cost. Therefore, MCT-LRC and MRCECT enable service differentiation b etween Class 1 and Class 2 tasks. 1.05 1 0.9 After the primary is scheduled, the time window on which its backup can b e scheduled is determined which is b etween the completion time of the primary and its deadline. Consequently, primary schedules and non-overloadable backup schedules that are within or overlap with the time window can b e identified. The backup can not overload with these two kinds of schedules and they partition the time window into a numb er of intervals on which the backup can b e scheduled. One such interval b etween tu and tv is shown in Figure 1 (a) where tu is the completion time of a primary schedule and tv is the start time of a non-overloadable backup schedule. There only exist overloadable backup schedules on each interval which can overload each other as shown in the figure. Now we address the problem of how to schedule a backup in an interval. We first consider sp ecial cases where its start time and/or finish time collide with b oundaries of the interval or b oundaries of overloadable backup schedules. These sp ecial cases are referred to as b oundary schedules and are lab eled as b-0 to b-5 in Figure 1 (b). Other p ossible cases are lab eled as c-1 to c-4 in Figure 1 (c) where its start time and/or finish time fall onto overloadable backup schedules and/or idle p eriods. Primary schedule Non-overloadable backup schedule Overloadable backup schedule Schedule for the current backup Acceptance Ratio 0.95 0.9 0.85 0.8 0.75 0.7 0.2 0.4 Load 0.6 0.8 Class1 Class2 Replication Cost 0.8 Class1 Class2 0.7 0.6 0 0.2 0.4 Load 0.6 0.8 0.5 Primary Response Time 0.4 Backup Response Time Class1 Class2 0.64 0.62 0.6 0.58 0.56 0.54 0.52 0.5 0 0.2 0.4 Load 0.6 0.8 Class1 Class2 0.3 0.2 0.1 0.2 0.4 Load 0.6 0.8 Figure 2: Performance of Class 1 and Class 2 tasks which are scheduled by MCT-LRC and MRC-ECT, respectively. 4. CONCLUSIONS P e tu (a) b-0 b-1 P e tu (b) c-1 c-2 c-3 c-4 tv t b-2 b-3 b-4 b-5 tv t In this pap er, for Grid systems, we addressed the problem of fault-tolerant scheduling for differentiated classes of indep endent tasks. Through simulation exp eriments, we demonstrated that MRC-ECT and MCT-LRC deliver good p erformance in terms of replication cost and completion time, resp ectively, and provide service differentiation for the two classes of tasks. P e tu (c) tv t 5. REFERENCES [1] I. Foster and C. Kesselman, Eds., The Grid: Blueprint for a Future Computing Infrastructure. 2nd Edition. Morgan Kaufmann Publishers, 2004. [2] R. Medeiros, W. Cirne, F. Brasileiro and J. Sauve, "Faults in Grids: Why are They so Bad and What Can Be Done about It?", in the 4th Workshop on Grid Computing, 2003. [3] I. Brandic, S. Benkner, G. Engelbrech and R. Schmidt, "QoS Support for Time-Critical Grid Workflow Applications", in the proceedings of the First International Conference on e-Science and Grid Computing (e-Science), 2005. [4] M. J. Gonzalez, "Deterministic Processor Scheduling," ACM Computing Surveys, vol. 9, no. 3, pp. 173-204, September 1997. [5] Q. Zheng, B. Veeravalli, and C. Tham, "Fault-tolerant Scheduling for Differentiated Classes of Tasks with Low Replication Cost in Computational Grids," Technical Report, http://cnds.ece.nus.edu.sg/QinZheng/hpdc.pdf. Figure 1: Scheduling a backup on an interval (a) overloadable backup schedules; (b) boundary schedules; (c) other possible schedules. Lemma 1. There exist only four possible cases c-1 to c-4 as in Figure 1 (c) for scheduling a backup other than boundary schedules. Lemma 2. Non-boundary schedules always have higher replication cost or the same replication cost but later completion time than boundary schedules. 240