We define a state interval, denoted by I(i,a), as the computation sequence between the (a-1)-th and the a-th synchronization operations of a process pi, where a > 1 and the 0-th synchronization operation means the initial state of pi. Then, in the LRC based DSM system, the computational dependency between the state intervals can be defined as follows:
Definition 1: A state interval I(i,a) is dependent on another state interval I(j,b) if any one of the following conditions is satisfied:
(a) i=j and a=b+1.
(b) I(j,b) ends with a release(x) and I(i,a) begins with an acquire(x), and pi in I(i,a) accesses a data page written by pj in I(j,b).
(c) I(j,b) ends with a barrier(x) and I(i,a) begins with the same barrier(x), and pi in I(i,a) accesses a data page written by pj in I(j,b).
(d) I(i,a) is dependent on I(k,c) and I(k,c) is dependent on I(j,b).
Definition 1.(a) indicates the natural dependency within a process, Definition 1.(b) and (c) present the inter-process dependency caused by accessing the common data page, and Definition 1.(d) states that the dependency relation is transitive.
Such dependency relation between the state intervals may cause possible inconsistency problems during the rollback-recovery. Figure 1 shows a typical example of inconsistent recovery case . The notations, R(X) and W(X), in the figure represent the read and the write operations on a data page X, respectively, and the notations U(A) and L(A) represent the release and the acquire operations on a lock A, respectively. Now, suppose that process pi should roll back to its latest checkpoint Ci due to its failure but it cannot regenerate the same computation for W(X). Then, the consistency between pi and pj becomes violated since pj's current computation depends on pi's computation invalidated by a rollback. Such a case is called an orphan state case and a process is said to recover to a consistent recovery line, if any process in the system is not involved in the orphan state case after the rollback-recovery.
Definition 2: A state interval I(i,a) is said to be an orphan, if for any interval I(j,b), I(i,a) is dependent on I(j,b) and I(j,b) is discarded by a rollback.
Definition 3: A process is said to recover to a consistent recovery line, if any state interval of the system is not an orphan after the rollback-recovery.