Analysis of checkpointing schemes for multiprocessor systems

Parallel computing systems provide hardware re-dundancy that helps t o achieve low cost fault-tolerance, by duplicating the task into more than a single pro-cessor, and comparing the states of the processors a t checkpoints. This paper suggests a novel technique, based on a Markov Reward Model (MRM) , f o r ana-lyzing the performance of checkpointing schemes with task duplication. W e show how this technique can be used to derive the average execution t ime of a task and other important parameters related t o the perfor-mance of checkpointing schemes. Our analytical re-sults match well the values we obtained using a simula-t ion program. W e compare the average task execution t ime and total work of f our checkpointing schemes, and show that generally increasing the number of pro-cessors reduces the average execution t ime, but in-creases the total work done by the processors. How-ever, i n cases where there i s a big difference between the t ime it takes t o perform different operations, those results can change.