Abstract: Risk-Tolerant Heuristic Scheduling for Trusted Grid Computing on Realistic Platforms *

Realistic platforms for Grid computing face security threats from the network attacks. Heterogeneous clusters in the open Grid are likely working in different autonomous domains (ADs). Grid jobs dispatched across the ADs are thus subject to unexpected failures or long delays due to wide-area insecurity. This hinders Grid job scheduling and outsourcing to remote sites. Unfortunately, this problem was largely ignored in the past. In this paper, we close up the gap by specifying several risk modes to model various levels of risky conditions in Grid sites. Then we propose three resilient strategies: preemptive, replication, and delay-tolerant for designing security-assured heuristic scheduling algorithms. The relative performance of these algorithms is evaluated by the NAS and PSA benchmarks. We measure the makespan, average turnaround time, Grid utilization, slowdown ratio, and job failure rate to evaluate heuristic algorithms. Kiviat graphs are used to demonstrate the highest performance of two delay-tolerant algorithms. Two replication algorithms rank the next, followed by two preemptive algorithms. The conservative algorithm has the lowest performance. These findings suggest that it is more resilient for the global job scheduler to tolerate job delays by calculated risky conditioning, instead of resorting to job preemption, replication, or assuming unrealistic risk-free operations. Index Terms: Grid computing, security binding, risk analysis, scheduling heuristics, heterogeneous computing, preemptive, replication, and delay-tolerant strategies, fault-tolerant computing, and distributed computin