A Recovery Sequence Generation System for Design of Recoverable Protocols

Yoshiaki KAKUDA  

IEICE TRANSACTIONS on Information and Systems   Vol.E74-D   No.6   pp.1715-1727
Publication Date: 1991/06/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fault Tolerant Computing

Full Text: PDF(948.5KB)>>
Buy this Article

In this paper, a scheme for recoverability of protocols, which have more than one process and can be modelled by communicating finite state machines, is studied. Normal operating states of a protocol are defined as the set of global states that can be reached by executing state transitions in which error events have not occurred. After some error events have occurred, sequences of state transitions enter abnormal operating states. If the protocol is recoverable, then the sequences revert back to a normal operating state. In real recoverable protocols, the sequences often return to a typical normal operating state, that is, an initial state while retaining consistency in the exchange of messages. This paper proposes a new rollback-recovery scheme for recoverable protocols. In this scheme, the sequences can return not only to an initial state but also to an intermediate state which was reached in the past while retaining consistency in the exchange of messages. In addition, protocols can efficiently return to the intermediate state using a broadcast mechanism. The proposed scheme is therefore effective for recoverability of protocols with more than one process. This paper also presents a recovery sequence generation system which has been developed for designing recoverable protocols and some experiments are carried out to show effectiveness of the proposed scheme.