distributed fault recovery

Please read slides on fault recovery alogrithm prepared by Prof. Gagan first.

Claim: Orphan messages are not acceptable by this algorihm.

Assume an orphan message M exit between thread Y and Z. Without the loss of generality, consider Z as the sender and Y as the receiver. By definition of orphan message, M must be sent after and received before . By the checkpoint algorithm, no message is allowed to sent at the interval between tentative point and commit point. Thus, M could only be sent after . In other words, and .

By checkpoint algorithm, we could obtain the conclusion . Revisit the relations at the end of above paragragh, the final time chain would be .

Contradiction: The sending time is larger than the receiving time!