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 [6].
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.