Patent ID: 8627322

Claim:
A computer-implemented method executable by a processor for allocating backup tasks to a plurality of tasks scheduled to run in a computer cluster, the method comprising: classifying the plurality of scheduled tasks into one or more task groups based on one or more resource requirements associated with each task, each task group containing at least one of the scheduled tasks; determining, for at least a respective one of the task groups, a number of backup tasks necessary to guarantee that the scheduled tasks of the respective task group satisfy a target probability for execution; and the processor generating the backup tasks based on the determined number of backup tasks, where the generated backup tasks for the respective task group are all identical, and each generated backup task in the respective task group is configured such that it can replace any scheduled task in the respective task group, wherein determining the number of backup tasks comprises: calculating a probability of losing no more than all current backup tasks in a given one of the plurality of task groups; comparing the calculated probability to the target probabilities for execution of the tasks in the task group; in response to a comparison outcome indicating that the calculated probability is greater than or equal to all the target probabilities, adding one backup task to a class of the given task group and performing said steps of calculating and comparing again; and in response to a comparison outcome indicating that the calculated probability is less than all the target probabilities, ceasing to add backup tasks to the given task group and performing said steps of calculating and comparing again.