DYNAMIC CHECKPOINTING PROCEDURE FOR THE DESIGN OF STABILIZING PROTOCOLS

In this paper, the problem of designing stabilizing computer communication protocols is addressed. A communication protocol is said to be stabilizing, if starting from or being at any illegal global state, the protocol will eventually reach a legal (or consistent) global state, and resume its normal execution. To achieve protocol stabilization, the protocol must he able to detect the error when it occurs, and then it must recover from that error and revert to a legal protocol state. Based on the concepts of event indices and maximally reachable event index tuples, we propose a novel approach for distributed dynamic checkpointing in which the overhead associated with the more traditional periodic checkpointing techniques is avoided. Furthermore, our checkpointing technique can be used as the basis for optimal protocol recovery to achieve stabilization. An example illustrating the new dynamic checkpointing technique is also provided.