An Effective Bi-Criteria and Contention Awareness Scheduling in Heterogeneous Distributed Systems

Abstract

Fault-tolerant scheduling is an important issue for optimal heterogeneous distributed systems because of a wide range of resource failures. In this paper we propose a fault-tolerant scheduling heuristics for precedence task that is based on primary-backup replication scheme on a realistic platform model where communication contention is taken into account. We focus on a bi-criteria approach, where we aim at minimizing makespan (or the schedule length), and the other way take account into the failure probability of the application. We are able to let the user choose atrade-off between reliability maximization and makespan minimization. Major achievements include a low complexity and reduction of the number of additional communications by the replication and clustering mechanism. Simulation results show that in comparison to existing scheduling algorithms, the proposed scheduling algorithm improves the reliability and performance.

Key Words:

• Fault-tolerant
• Primary-backup
• Communication contention
• Reliability