Checkpointing algorithms and fault prediction

• We have improved the text in many places, based upon all the suggestions.
• We have added a new set of simulations based upon actual failure traces.
• We have added a new set of simulations to deal with inaccurate prediction dates.

This paper deals with the impact of fault prediction techniques on checkpointing strategies. We extend the classical first-order analysis of Young and Daly in the presence of a fault prediction system, characterized by its recall and its precision. In this framework, we provide optimal algorithms to decide whether and when to take predictions into account, and we derive the optimal value of the checkpointing period. These results allow us to analytically assess the key parameters that impact the performance of fault predictors at very large scale.