Rollback recovery schemes for distributed systems
Zhijun Tong · 1990
Recently, distributed systems have become increasingly popular to satisfy requirements for increased computing power. In distributed systems recovery from individual component failures becomes critical because of the increased number of independent failure points compared to a single processor. One of the major issues of reliable distributed system design is to provide capability of fault recovery without having to restart the whole task. In this thesis we propose rollback recovery schemes for distributed systems. We divide distributed systems into multiprocessor and distributed processing systems. In multiprocessor systems we assume that a global timing device is available. We present two hardware rollback recovery schemes aimed at minimizing state saving overhead. We also presented two state-save synchronization protocols. Protocol 1 is simple, but it introduces a waiting time. Protocol 2 eliminates the waiting time, but its implementation is more complicated than Protocol 1. For distributed processing systems we develop a rollback recovery scheme aiming at minimizing state saving synchronization overhead. The state-save synchronization among processes is implemented by using a local clock at each process and bounding the clock drifts such that no communication messages are required for the state-save synchronization. We also develop an interprocess communication protocol to assure that a consistent system state is always checkpointed. A protocol to replay backout messages in their original order using only a small amount of storage is also presented. The performance of systems with the proposed scheme is studied. For the rollback scheme developed for multiprocessor systems, closed form expressions for the mean and variance of a task execution time as well as approximate optimal value for the state-save interval are derived. For the rollback recovery schemes developed for distributed processing systems, an algorithm is presented to form numerical solutions.