Optimal and suboptimal reliable scheduling of precedence-constrained tasks in heterogeneous distributed computing

Introduces algorithms which can produce both optimal and suboptimal task assignments to minimize the probability of failure of an application executing on a heterogeneous distributed computing system. A cost function which defines this probability under a given task assignment is derived. To find optimal and suboptimal task assignments efficiently, a reliable matching and scheduling problem is converted into a state-space search problem in which the cost function derived is used to guide the search. The A* algorithm for finding optimal task assignments and the A*_m and hill-climbing algorithms for finding suboptimal task assignments are presented. Simulation results are provided to confirm the performance of the proposed algorithms