Fault Tolerant Scheduling of Interval Ordered Tasks with Communication in a Multiprocessor System

M. Desiraju and H.H. Ali (USA)


Scheduling, Fault Tolerance, Communication delay, Interval Order task graph, Primary task, Backup task.


This work is intended to present an efficient technique to produce a fault tolerant schedule for a task graph while considering communication costs. It is well known that when communication costs are considered, optimal algorithms exist for special cases like Interval Ordered graphs and Tree structured graphs on two processors [1, 2, 3]. Following this fact, this paper provides an optimal Fault Tolerant schedule for the Interval Graphs and a near optimal Fault Tolerant schedule for the non-Interval Order graphs by converting them into Interval Orders. The importance of this algorithm is that the communication costs are not ignored.

Important Links:

Go Back