RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 5 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

A MODEL OF
ROLL-BACK RECOVERY
WITH
MULTIPLE CHECKPOINTS

E. Gelenbe

Rapport de Recherche N°169

Avril 1976
A MODEL OF ROLL-BACK RECOVERY WITH
MULTIPLE CHECKPOINTS*

E. Gelenbe

IRIA/LABORIA

Résumé :

Cet article est consacré à une analyse, par l'utilisation d'un modèle mathématique, des performances d'un système informatique utilisant des points de reprise pour assurer son fonctionnement fiable en présence de défaillances. On considère le cas où une hiérarchie de défaillances et de points de reprise existe.

Abstract :

A stochastic model of a transaction oriented computer system in the presence of intermittent failures, operating with a checkpoint and roll-back recovery scheme, is proposed in the case of a hierarchy of checkpoints and failures. An analysis provides the stationary probability distribution for the model and the optimum checkpoint intervals for two cases of interest : when a fixed checkpoint is used for each failure and when the allowable checkpoint closest in time is used.

* Invited paper, Second ACM-IEEE International Conference on Software Engineering, Oct. 13-15 1976, San Francisco.

Communication invitée au Deuxième Colloque International ACM-IEEE sur l'Ingénierie du Logiciel, 13-15 Octobre 1976, San Francisco.
# 0 - INTRODUCTION

In this paper we model a transaction oriented computer system operating in the presence of intermittent failures. In order to ensure the validity of the data stored in the system, a checkpointing scheme is used in the information system under consideration : at predetermined instants of time all the valid data is saved in an area (some secondary memory device) which cannot be affected by the failures. This is called a *checkpoint*. When a failure occurs, and assuming that it is immediately detected, all transactions which have been processed since the most recent checkpoint (or rather, all those which modify the data) are reprocessed after copying the data stored at the checkpoint back in main memory. This is known as reprocessing the audit trail or *roll-back recovery*. Clearly, an optimum is to be found in the frequency with which checkpoint are established : frequent checkpoint will contribute to the overhead but reduce the cost in computer time of roll-back recovery after failure.

Recent papers [1 - 3] have been concerned with the choice of the optimum checkpoint interval. In [4] we have analyzed a queueing model of such a system in order to compute the response time and other relevant statistics of the system in stationary state.

In this paper we are concerned with various *types* of failures. A failure of type i, $1 \le i \le n$, will cause a rollback recovery to take place using a checkpoint of type j, $1 \le j \le n$. A larger value of i or j denotes a:
failure which is more "difficult" to repair and a more "powerful" checkpoint, respectively. Our purpose is to examine the effect of using a fixed checkpoint, or of the closest allowable checkpoint, on the availability and other performance measures of the system. A comparison paper [5] is devoted to some optimal policies.

In Section 1 we solve a queueing model which will be of use to us in our analysis. Section 2 will develop the model of the transaction oriented system.

# 1 - A Markov chain dependent server

Consider the continuous time ergodic Markov chain with state set {0, 1, ..., m} and transition rate matrix P = ($p_{ij}$) where

$$p_{0j} = \alpha_j, \quad 1 \le j \le m$$

$$p_{j0} = \beta_j, \quad 1 \le j \le m$$

$$ (1) \quad p_{ij} = 0, \quad i \neq j, i \neq 0, j \neq 0 $$

$$p_{00} = - \sum \alpha_j$$

$$p_{ii} = - \beta_i, \quad i \neq 0$$

Σ denotes in this section $Σ_1^m$. Of course, the $α_j$ and $β_j$ are positive and finite. This Markov chain conditions the service provided to a single-server queue whose customer arrival process is Poisson of parameter $λ$. Let $M_t$ denote the state of the above chain at time t. If $M_t = 0$, then the service time of the queue is exponentially distributed of parameter $μ$. If $M_t = 1, ..., m$, then the server is turned off. Let $N_t$ be the number of customers in queue at time t and denote

$$p(n, k, t) = \text{Pr}\{N_t = n, M_t = k | N_0, M_0\}.$$
Let $p(n, k) = \lim_{t \to \infty} p(n, k, t)$, when it exists. We establish the following results.

**Theorem 1** : The $p(n, k) > 0$, such that the sum of the $p(n, k)$ over all $(n, k) \in \mathbb{N}^+ \times \{0, 1, ..., m\}$ is one, exist $\underline{iff} \ \mu > \lambda [1 + \Sigma \alpha_j/\beta_j]$.

**Theorem 2** : Let $G_k(x) = \sum_{n=0}^{\infty} p(n, k) x^n, |x| \le 1, k \in \{0, 1, ..., m\}$. They are given by

$$G_0(x) = \frac{\mu(1-\frac{1}{x}) (A-\lambda/\mu)}{\lambda(1-x) + \mu(1-\frac{1}{x}) - \Sigma\alpha_j + \Sigma\alpha_j\beta_j / [\lambda(1-x) + \beta_j]}$$

and

$$G_i(x) = \alpha_i G_0(x) / [\lambda(1-x) + \beta_i], \quad i = 1, ..., m, \text{ where}$$

$$A = [1 + \Sigma \alpha_j / \beta_j]^{-1}.$$

The proof is established by considering the transition equations in stationary state of the Markov chain $(N_t, M_t)_{t \in \mathbb{R}^+}$. They are

$$(2) \quad p(n, 0) (\lambda + \Sigma \alpha_j + \mu) = \lambda p(n-1, 0) + \mu p(n+1, 0) + \Sigma \beta_j p(n, j)$$

for $n > 0$, and

$$p(0, 0) (\lambda + \Sigma \alpha_j) = \mu p(1, 0) + \Sigma \beta_j p(0, j)$$

and for $i \neq 0$,

$$(3) \quad p(n, i) (\lambda + \beta_i) = \lambda p(n-1, i) + \alpha_i p(n, 0)$$
when $n > 0$, and

$$p(0, i) (\lambda + \beta_i) = \alpha_i p(0, 0)$$

The generating functions then satisfy the equations :

$$(4) \quad G_0(x) [\lambda(1-x) + \mu(1-1/x) + \Sigma\alpha_j] = \mu(1-1/x) p(0, 0) + \Sigma\beta_j G_j(x)$$

$$(5) \quad G_j(x) [\lambda(1-x) + \beta_j] = \alpha_j G_0(x), \quad 1 \le j \le m.$$

Therefore

$$(6) \quad G_0(x) = \frac{\mu(1-1/x) p(0, 0)}{\lambda(1-x) + \mu(1-1/x) + \Sigma\alpha_j - \Sigma\alpha_j\beta_j / [\lambda(1-x) + \beta_j]}$$

But $G_0(1)$ is the stationary probability of state 0 of the Markov chain $(M_t)_{t \in \mathbb{R}^+}$. Therefore after applying l'Hôpital's rule to (6) at $x = 1$ and using
$$G_0(1) = A = [1 + \Sigma\alpha_j/\beta_j]^{-1},$$

$$(7) \quad p(0, 0) = A - \lambda/\mu$$

establishing Theorem 2. Since $(M_t, M_{t+1})_{t \in \mathbb{R}^+}$ is an aperiodic and irreducible chain, $p(n, k) > 0$ for any $(n, k)$ if $p(0, 0) > 0$ which is the case when $\lambda/\mu < 1$ or $\mu > \lambda[1 + \Sigma\alpha_j/\beta_j]$. It remains to show that $0 < G(1) < \infty$ iff $\lambda/\mu < A$, where $G(x) = \sum_{k=0}^{m} G_k(x)$. Notice that

$$(8) \quad G(x) = G_0(x) [1 + \Sigma\alpha_j / (\lambda(1-x) + \beta_j)]$$

It is easily seen that if $A > \lambda/\mu$ then $G(1) = 1$. If $A = \lambda/\mu$, or $A < \lambda/\mu$, we must have $p(0, 0) = 0$ leading to $p(n, k) = 0$ for all finite $n$.
To complete this analysis, we compute from (8) the expected value of the number of customers in queue in stationary state $E\{N_\infty\}$ by using $E\{N_\infty\} = G'(1)$. This yields, after some algebra,

$$ (9) \quad E\{N_\infty\} = \frac{(\lambda/\mu) + \lambda A^2 \sum \alpha_j / \beta_j^2}{A - \rho} $$

and the expected response time $W$, in stationary state, to a customer is readily obtained from Little's formula $W = \lambda^{-1}E\{N_\infty\}$.

The expression for $E\{N_\infty\}$ in (9) calls for a remark. Recall that the expected number of customers in queue for the M/M/1 system is given by $(\lambda/\mu)/[1 - \lambda/\mu]$. Therefore if we had not gone through this analysis we might have been tempted by the following "approximate" argument : let us imagine that the net effect of the Markov chain dependent server is to replace the service rate $\mu$ by $A\mu$, where A is the "availability" of the server. We then might use the expression for the M/M/1 system and say that

$$ (10) \quad E\{N_\infty\} \approx \frac{\lambda/\mu A}{1 - \lambda/\mu A} = \frac{\lambda/\mu}{A - \lambda/\mu} $$

We see easily that the approximation in (10) is very poor unless $\mu^{-1} \gg A^2 \sum \alpha_j / \beta_j^2$. This, from a "practical" standpoint, justifies the use of our analysis.

Some quantities related to the Markov chain $(M_t)_{t \in \mathbb{R}^+}$

In the model of the transaction oriented computer system operating under intermittent failures to be presented in Section 2, we shall need some quantities related to the process $(M_t)_{t \in \mathbb{R}^+}$ which controls the server.

Let $t$ be any instant of time such that $M_t = 0$, and for some set of states $E \subseteq \{1, 2, \dots, m\}$ of $(M_t)_{t \in \mathbb{R}^+}$ (notice that $0 \notin E$), let $t_E$ be the time instant

$$ (11) \quad t_E = \{ \sup \tau : \tau < t \text{ and } M_\tau \in E \} $$
For any instant $\tau \in \mathbb{R}^+$, let $u(\tau) = 1$ if $M_\tau = 0$ and $u(\tau) = 0$ otherwise. We define

$$ (12) \qquad T(t, E) = \int_{t_E}^{t} u(\tau) \, d\tau $$

In simple terms, $T(t, E)$ is the total time spent in state 0 by the Markov chain between the last time it was in a state of E preceding time $t$ and the instant $t$. For any $t$ and $E$ we are interested in the probability distribution function (pdf) of $T(t, E)$. If $E$ contains more than one state, we shall denote this pdf.

$$ (13) \qquad F_{t,E}(x) = \Pr\{T(t, E) \le x\} $$

Otherwise if $E = \{i\}$, $1 \le i \le m$, we shall denote it $F_{t,i}(x)$.

Let us first compute the pdf of the total time $Q$ spent in state 0 between two consecutive sejourns in a state of E. From (1) we know that any single sejourn in 0 is exponentially distributed of parameter $\Sigma\alpha_j$. With probability $\Pi$, where

$$ \Pi = \sum_{j \in E} \alpha_j / \sum \alpha_j $$

at the end of a sejourn in state 0 the chain $(M_t)_{t \in \mathbb{R}^+}$ enters a state of E; therefore the Laplace transform of the probability density function of $Q$ is

$$ (14) \qquad g^*(s) = \sum_{k=1}^{\infty} (1-\Pi)^{k-1} \Pi\left(\frac{\Sigma\alpha_j}{s + \Sigma\alpha_j}\right)^k $$

therefore the pdf is $G(x) = 1 - \exp(-x\Pi \Sigma\alpha_j)$.

Let $V(\tau) = 1$ if $M_\tau \notin \{0\} \cup E$ and $V(\tau) = 0$ otherwise. For any instant of time $\tau$ we define

$$ \tau^* = \tau - \int_{0}^{\tau} V(y)dy $$
Let $\xi_i$, $i = 1, 2, \dots$, be the instant of the i-th passage of the Markov chain into a state of E, and denote by $\Psi_i$ the corresponding residence time in the state of E. Then

$$ (15) \qquad F_{t,E}(x) = \sum_{i=1}^{\infty} \Pr\{t^* - x \le (\xi_i + \Psi_i)^* < t^* < \xi_{i+1}^*\} $$

which may be written as

$$ F_{t,E}(x) = \sum_{i \ne 1}^{\infty} \int_{t^*}^{t^*-x} \Pr\{\xi_{i+1}^* - (\xi_i + \Psi_i)^* \ge t^* - u\} \cdot d\Pr\{(\xi_i + \Psi_i)^* \le u\} $$

But, using (12), it has been shown that

$$ (16) \qquad \Pr\{\xi_{i+1}^* - (\xi_i + \Psi_i)^* \ge t^* - u\} = \exp(-(t^* - u) \Pi \Sigma \alpha_j) $$

for any i. Also, for large enough u

$$ (17) \qquad \sum_{i=1}^{\infty} d\Pr\{\xi_i + \Psi_i)^* \le u\} \rightarrow du[(\Pi\Sigma\alpha_j)^{-1} + \sum_{j \in E} (\alpha_j/\beta_j)/\sum_{j \in E} \alpha_j]^{-1} $$

To prove (17) it suffices to notice that the sequence of instants $\{(\xi_i + \Psi_i)^*\}_{i=1, 2, \dots}$ forms a renewal process : it is the sequence of instants of entry into state 0 if we eliminate the epochs of residence in states other than 0 and all $j \in E$ for the Markov chain. The inter-event times are independent and identically distributed of expected value

$$ (\Pi\Sigma\alpha_j)^{-1} + \sum_{j \in E} (\alpha_j/\beta_j)/\sum_{j \in E} \alpha_j $$

Hence the left-hand side of (17) is the density of the number of renewals, yielding the expression on the right-hand side. Therefore (15) becomes for t large

$$ (18) \qquad F_{t,E}(x) = \frac{1}{1 + \sum_{j \in E} \alpha_j / \beta_j} (1 - \exp(-x \Pi \Sigma \alpha_j)) $$
We are interested in the distribution of $T(t, E)$ given that $M_t = 0$. This is simply

$$ (19) \qquad \hat{F}_{t,E}(x) = 1 - \exp(-x\Pi\Sigma\alpha_j) $$

which is independent of $t$.
## 2 - Analysis of the roll-back/recovery strategy

As stated previously, n types of failures can occur in our system : for $1 \le i \le n$, a failure of type i takes place at instants described by a Poisson process of parameter $\gamma_i$. A type i failure can will cause the system to interrupt its normal service operation in order to execute a proportion $\delta_i$ of all transactions which have been processed since a checkpoint of type j, $j \ge i$, has been established. The assumption is implicit that there is a hierarchy of failures and of checkpoints. We shall consider various policies for choosing the appropriate checkpoint for recovery after a failure.

Transaction requests arrive to the system according to a Poisson process of rate $\lambda$. We also assume that while a checkpoint is established, as well as during roll-back/recovery, normal transaction processing cannot take place. However, during other periods the system processes transactions on a first-come-first-served basis and each transaction is treated in a time which is exponentially distributed of parameter $\mu$.

Returning to the Markov chain $(M_t)_{t \in \mathbb{R}^+)$ of Section 1, we shall take $m = 2n+1$, and state 0 will correspond to normal operation while states 1, ..., n will represent the intervals during which checkpoints of type 1, ..., n are established, respectively. Thus $\alpha_i^{-1}$, $1 \le i \le n$, will be the average duration of normal transaction processing which separates the end of a checkpoint of type i and the beginning of the next checkpoint of same type. $\beta_i^{-1}$, $1 \le i \le n$, will be the average time duration for establishing a type i checkpoint.

States $j$ for $n+1 \le j \le 2n$ will be entered when a failure of type $j$ occurs, so we shall replace $\alpha_{i+n}$ by $\gamma_i$ for $1 \le i \le n$. Also $\varphi_i^{-1}$ (that is $\beta_{i+n}^{-1}$ for $1 \le i \le n$) will be used to denote the average time for recovery from a type $i$ failure.

By adopting the Markov chain $(M_t)_{t \in \mathbb{R}^+}$ as the failure and recovery, and checkpointing, model of the computer system under consideration we are assuming that the inter-checkpoint intervals of normal operation, the recovery
times and the times for establishing checkpoints, are exponentially distributed.

We shall analyze two policies in this paper :

(i) the case when recovery a failure of type i makes use of the type i checkpoint,

(ii) the case when the type j, j ≥ i, checkpoint closest in time to the type i failure occurrence is used.

Policies (i) and (ii) are analyzed below, while the minimum cost policy is discussed in a separate paper [5].

### A fixed checkpoint for each failure

Let us first consider the simplest case : recovery from a failure is achieved by the use of a checkpoint of the same type. Using (19) we know that if the time t of occurrence of the failure is sufficiently large then the pdf of the duration of the normal operation time between the instant of occurrence of the failure and the time at which the most recent checkpoint of type i had been established, is

$$ (20) \quad \hat{F}_{t,i}(x) = 1 - \exp(-x\alpha_i) $$

and we denote the length of this time interval by $T(t,i)$.

In stationary state, the probability that the server is busy given that it is in state 0 (i.e. in normal operation) is $[G_0(1) - p(0,0)]/G_0(1) = \lambda/\mu A$, as is easily seen from (6), (7). Therefore in a time interval of length $T(t,i)$ spent in normal operation the average number of transactions processed is approximately $[\mu T(t,i)](\lambda/\mu A)$, or $\lambda T(t,i)/A$. Assuming that $\delta_i$ is the fraction of these which need reprocessing after a type i failure, and using (20), we see that the average reprocessing time can be approximated by $\lambda\alpha_i^{-1}\delta_i K/A$
where K is the reprocessing time per transaction.

We shall take the average roll-back/recovery time from a type i
failure as being

$$
(21) \quad \varphi_i^{-1} = C_i + \lambda K \alpha_i^{-1} \delta_i / A
$$

where Cᵢ may be a cost term incurred due to the need of copying back into main memory the safe information which is stored at a checkpoint of type i. A more exact analysis, which appears analytically intractable would have included a more accurate model of the "audit trail", i.e. of those transactions which have been processed since the last set of checkpoints and which will have to be reprocessed after a failure.

The "availability" A of this system (A = G₀(1)), now becomes (using Theorem 2),

$$
(22) \quad A = \left[ 1 + \sum_{i=1}^{n} \frac{\alpha_i}{\beta_i} + \sum_{i=1}^{n} \frac{\lambda K \gamma_i \delta_i}{A \alpha_i} + \sum_{i=1}^{n} C_i \gamma_i \right]^{-1}
$$

Notice that A appears on both sides of (22). After simplification we have

$$
(23) \quad A = \frac{1 - \sum_{i=1}^{n} \frac{\lambda K \gamma_i \delta_i}{\alpha_i}}{1 + \sum_{i=1}^{n} \frac{\alpha_i}{\beta_i} + \sum_{i=1}^{n} C_i \gamma_i}
$$

The *optimum checkpoint interval problem* which is the determination of the values of α₁, ..., αₙ which maximize A is important. The differences with the equivalent problem examined in [1 - 3] are that we have n checkpoint types rather than just one, and that due to the queueing model used here A intervenes on both sides of (22) changing the nature of the optimum.

The αᵢ in (23) are independent variables. Therefore we set (∂A/∂αᵢ) = 0 for each 1 ≤ i ≤ n. A is maximized by setting the αᵢ, 1 ≤ i ≤ n, to the
following optimum values if the $C_i = 0$ :

$$ (24) \qquad \alpha_i^* = \left[ \frac{\lambda K \gamma_i \delta_i \beta_i}{1 + \sum_1^n \alpha_i^* / \beta_i} \right] / \left( 1 - \sum_1^n \frac{\lambda K \gamma_i \delta_i}{\alpha_i^*} \right)^{1/2} $$

The system of equations (24) does not have a simple analytical solution. A first order approximation to (23) :

$$ (25) \qquad A \approx 1 - \sum_{i=1}^{n} \left[ \left( \frac{\alpha_i}{\beta_i} \right) + \frac{\lambda K \gamma_i \delta_i}{\alpha_i} \right] $$

is justified, however, for values of A close to 1. The optimum checkpoint parameters then become for $C_i = 0, 1 \le i \le n$,

$$ (26) \qquad \alpha_i^* \approx \left( \frac{\lambda K \gamma_i \delta_i \beta_i}{n} \right)^{1/2} $$

which is quite similar to the form obtained in [1 - 3] for one type of checkpoint. Notice that close to the optimum, the approximation (25) will be more accurate. We then have, for the optimum value of A,

$$ (27) \qquad A^* \approx 1 - \sum_{i=1}^{n} 2 \sqrt{\frac{\lambda K \gamma_i \delta_i}{\beta_i}} $$

It is of interest to compare (27) with the corresponding quantity with one type of checkpoint :

$$ (28) \qquad A_1^* \approx 1 - 2 \sqrt{\frac{\lambda K g}{\beta_n}} $$

where $g = \sum_{i=1}^{n} \gamma_i \delta_i$ : a checkpoint of type n has to be used at all times in order to be able to recover from all failures. Assuming that $\beta_n^{-1} > \beta_i^{-1}$, $1 \le i \le n-1$, it can be seen that the approximate value of (27) is smaller than that of (28), showing that system availability can be enhanced by the use of several types of checkpoints.
When $\mathcal{C}_i \neq 0$, the approximate optimum checkpoint parameters of (26) remain valid, but we now have

$$ (29) \quad A^* \approx 1 - \sum_{i=1}^{n} \left( 2\sqrt{\frac{\lambda K Y_i \delta_i}{\beta_i}} + \mathcal{C}_i \right) $$

Using these parameters and (9) we will obtain the expected number of transactions in queue in stationary state :

$$ (30) \quad E\{N_\infty\} = \frac{(\lambda/\mu) + \lambda(A^*)^2 \left[ \sum_1^n \gamma_i \mathcal{C}_i^2 + \sum_1^n (\lambda K Y_i \delta_i)^{1/2} / \beta_i^{3/2} \right]}{A^* - (\lambda/\mu)} $$

## The use of the closest allowable checkpoint

Among all types of checkpoints ($j \ge i$) which may be used to recover from a failure of type i, a reasonable policy in some cases is to choose the one which is closest in time to the instant of failure. This approach would be appropriate if, for instance, the cost of reprocessing the audit trail were only a function of the number of transactions it contained, or if the imperative were to minimize the size of the audit trail to be stored.

The analysis is again largely based on Section 1.

Here recovery from a failure of type i is achieved by using the closest checkpoint of type j, $j \ge i$. Let $E_i = \{j | i \le j \le n\}$. Thus the total time spent in state 0 (the duration of normal operation) separating a failure which has occurred at time t (during normal operation) and the "closest" checkpoint has $\hat{F}_{t, E_i}(x)$. With probability

$$ \theta_{\ell} = \alpha_{\ell} / \sum_{j \in E_i} \alpha_j, \quad \ell \in E_i $$

an $\ell$-type checkpoint will be used, among all allowable checkpoints.
First notice that the average time separating the failure from
the closest allowable checkpoint is $(\sum_{j \in E_i} \alpha_j)^{-1}$. Using an argument similar
to the one leading to (21), we will take that the average time necessary to
recover from a type i failure is now

$$
(31) \quad (\varphi_i)^{-1} = \sum_{\ell \in E_i} \theta_{\ell} [C_{\ell} + \lambda K (\sum_{j \in E_i} \alpha_j)^{\ell-1} \delta_{\ell/A'}]
$$

where the availability A' of the system is then

$$
(32) \quad A' = \left[ 1 + \sum_{i}^{n} \alpha_i / \beta_i + \sum_{i}^{n} \gamma_i / \varphi_i \right]^{-1}
$$

and after simplification

$$
(33) \quad A' = \frac{1 - \sum_{\ell \in E_i}^{n} \sum_{\alpha_i / \beta_i} \theta_{\ell} \lambda K \delta_{\ell} \gamma_i / (\sum_{j \in E_i} \alpha_j)}{1 + \sum_{\ell \in E_i}^{n} \sum_{\alpha_i / \beta_i} \theta_{\ell} C_{\ell} \gamma_i}
$$

The computation of the checkpoint intervals which minimize A in
this case seems very complicated.

Of course, (33) can be used in (9) to obtain the average queue
length and the response time formula similar to (30).
3 - Conclusions

In this paper we have examined the effect of a commonly used
procedure for insuring reliable operation of data-base type systems on
the main performance measures of such systems.

With respect to [1 - 3], our approach is more general since we
provide a method of analysis of the system performance rather than just
a computation of optimum checkpoint intervals. Also we consider the
possibility of multiple checkpoints and failure types rather than just one,
as we had done earlier in [4]. With respect to [1 - 4] our analysis for
system availability also differs since we consider the fact that the
availability A will influence the number of transactions which have to
be reprocessed. This leads to a different expression for availability
itself : A given in (23) is different and more accurate than the corresponding
quantities provided in [1 - 4]. We also see that the optimum checkpoint
terval given in [1 - 4] is only a first-order approximation. Interestingly
enough, the optimum value of the checkpoint interval maximizing A does
not minimize other important performance measures, such as average queue
length (see (9)). In fact it may be shown without too much difficulty
$\partial E\{N_\infty\}/\partial\alpha_i > 0, 1 \le i \le n$, for $\alpha_i = \alpha_i^*$ of (24), and that the values of
$\alpha_i$ minimizing $E\{N_\infty\}$ are smaller than $\alpha_i^*$, $1 \le i \le n$ (larger checkpoint
intervals).

In [5] we examine the case where the optimum checkpoint is used
for each failure ; however our study may be generalized in several directions.
Some of these would include a more detailed model of the transaction
processing system or a more general model of the checkpoint and failure
mechanism.
REFERENCES

1 - K.M. CHANDY, J.C. BROWNE, C.W. DISSLY, W.R. UHRIG, "Analytic Models for Roll-back and Recovery Strategies in Data Base Systems", *IEEE Transactions on Software Engineering*, Vol. 1, N° 1, March 1975, pp. 100-110.

2 - K.M. CHANDY, "A Survey of Analytic Models of Roll-back and Recovery Strategies", *Computer*, Vol. 8, N° 5, May 1975, pp. 40-47.

3 - J.W. YOUNG, "A First Order Approximation to the Optimum Checkpoint Interval", *Comm. ACM*, Vol. 17, N° 9, September 1974, pp. 530-531.

4 - E. GELENBE, D. DEROCHETTE, "On the Stochastic Behaviour of a Computer System under Intermittent Failures", submitted to *Comm. ACM*.

5 - E. GELENBE, "Optimal Recovery with the Use of Checkpoints", in preparation.