ITS OPTIMAL IMPLEMENTATION
K. H. Kim · 1981
Rollback-and-ret ry is a technique of sav- ing computer system states at various checkpoints during program execution and, on detection of an error, reestablishing the computer system to a previously saved state and resuming program execu- tion. A novel rollback-and-ret ry scheme called a two-level rollback is dev,eloped in which two types of checkpoints are established for reduction of both time overhead and rcllback distance. The two types of checkpoints are called major checkpoints and minor checkpoint,^. Major checkpoints correspond to the checkpoints in existing single- level schemes. In order to establish minor checkpoints without incurring a significant amount of time overhead, p rogram execution and saving of minor checkpoint records (i.e.? information necessary for rollback) proceed in parallel,. This parallelism exploitation as well as compression of minor checkpoint records is realized by using a content-addressa ble memory as a buffer of the records transfered between a processor and a backup memory. Sometimes a multi-step rollback, i.e., backing up past t he most recent checkpoint, is executed to recover from a long latent error. An analytic model which reflects occurrences of long latent errors is then developed to support determination of an optimal c heckpoint interval as well as an optimal multi-step rollback s trategy.