<figure><img src="image_1.png" /></figure>

HAL
open science

# On the optimum checkpoint interval

Erol Gelenbe

► To cite this version:

Erol Gelenbe. On the optimum checkpoint interval. [Research Report] IRIA-RR-232, IRIA. 1977, pp.22. hal-04716479

HAL Id: hal-04716479

https://inria.hal.science/hal-04716479v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

ON THE OPTIMUM
CHECKPOINT INTERVAL

Erol GELENBE

Rapport de Recherche N° 232

Mai 1977
ON THE OTIMUM CHECKPOINT INTERVAL

Erol Gelenbe*

Résumé :

Le but de cet article est d'étudier les performances des procédures de reprise sur erreur en présence de points de reprise. Le modèle traité correspond à certains des aspects les plus importants des procédures de reprise du système de bases de données centralisées (tel que SOCRATE).

Les questions que nous abordons concernent :

- l'implantation optimale dans le temps des points de reprise (checkpoints) de façon à maximiser la disponibilité du système,

- le calcul de la charge maximale (en nombre de transactionstraitées par unité de temps) que peut
supporter le système en présence du mécanisme qui assure sa fiabilité, mais qui bloque son fonctionnement normal aussi bien pendant l'implantation des points de reprise que pendant la reprise
sur erreur.

Une solution complète à ces deux problèmes est donnée dans le contexte du modèle. Nous démontrons que le temps total de fonctionnement normal du système entre deux points de reprise successifs doit être constant pour maximiser la disponibilité. Nous donnons également une formule explicite de ce temps : cette formule dépend de la charge du système.

Le modèle étudié contribue également à n'cs connaissances concernant les files d'attente avec
pannes. En effet, il s'agit d'un système d'attente pour lequel le temps de réparation de la panne
est fonction de l'âge de la panne par rapport à la dernière période de maintenance.

Abstract :

In this paper we consider a mathematical model of a transaction oriented computing system (airline reservation system, file system, data-base system, etc ...) operating in the presence of intermittent failures, and with a checkpoint and roll-back recovery scheme built-in to preserve system integrity. An arbitrary distribution of inter-checkpoint times is assumed. We compute the system availability under some broad assumptions. We prove that it is maximized if the total time of normal operation between successive checkpoints is deterministic, and derive its optimum value. The queueing process representing the backlog of transactions to be processed by the system is analyzed and necessary and sufficient conditions for its ergodicity are proved. The stationary probability that the queue of request is empty is obtained. This leads to a finer analysis of the availability of the system which takes into account the fact that the recovery time from a failure is a function of the actual work done by the server since the most recent checkpoint, and to a more precise formula for the optimum checkpoint interval.

The model which we study and the results obtained are also new in the context of reliability theory. We are dealing with a queue with service interruptions for maintenance and for repairs of failures. The time for repair of a failure is assumed to be a function of the age of the failure with respect to the most recent maintenance epoch.
ON THE OPTIMUM CHECKPOINT INTERVAL

Erol Gelenbe

Département de Mathématiques
Université Paris-Nord
Avenue J.-B. Clément
93 Villetaneuse

O - Summary

In this paper we consider a mathematical model of a transaction oriented computing system (airline reservation system, file system, data-base system; etc.) operating in the presence of intermittent failures, and with a checkpoint and roll-back recovery scheme built-in to preserve system integrity. An arbitrary distribution of inter-checkpoint times is assumed. We compute the system availability under some broad assumptions. We prove that it is maximized if the total time of normal operation between successive checkpoints is deterministic, and derive its optimum value. The queueing process representing the backlog of transactions to be processed by the system is analyzed and necessary and sufficient conditions for its ergodicity are proved. The stationary probability that the queue of requests is empty is obtained. This leads to a finer analysis of the availability of the system which takes into account the fact that the recovery time from a failure is a function of the actual work done by the server since the most recent checkpoint, and to a more precise formula for the optimum checkpoint interval.

The model which we study and the results obtained are also new in the context of reliability theory. We are dealing with a queue with service interruptions for maintenance and for repairs of failures. The time for repair of a failure is assumed to be a function of the age of the failure with respect to the most recent maintenance epoch.
Résumé

Le but de cet article est d'étudier les performances des procédures de reprise sur erreur en présence de points de reprise. Le modèle traité correspond à certains des aspects les plus importants des procédures de reprise du système de bases de données centralisées (tel que SOCRATE).

Les questions que nous abordons concernent :

- l'implantation optimale dans le temps des points de reprise (checkpoints) de façon à maximiser la disponibilité du système,

- le calcul de la charge maximale (en nombre de transaction traitées par unité de temps) que peut supporter le système en présence de méchanisme qui assure sa fiabilité, mais qui bloque son fonctionnement normal aussi bien pendant l'implantation des points de reprise que pendant la reprise sur erreur.

Une solution complete à ces deux problèmes est donnée dans le contexte du modèle. Nous démontrons que le temps total de fonctionnement normal du système entre points de reprise doit être constant pour maximiser la disponibilité. Nous donnons également une formule explicite de ce temps : cette formule dépend de la charge du système.

Le modèle étudié contribue également à nos connaissances concernant les files d'attente avec pannes. En effet, il s'agit d'un système d'attente pour lequel le temps de réparation de la panne est fonction de l'age de la panne par rapport à la dernière période de maintenance.
# 1 - Introduction

The model we analyze in this paper arises in the context of reliability theory in general. Our motivation is due to the fact that it appears in the study of reliable data-base systems and transaction oriented computer systems.

Consider a data-base system (the server) which executes transactions (the customers) arriving to it in first-come-first-served order. In such systems it is essential to be able to reconstitute the contents of the primary memory to its correct state after a failure occurs which invalidates memory contents. To this effect each transaction is stored in the *audit trail*; a *checkpoint* is established from time to time, and after a failure all transactions stored in the audit trail since the most recent checkpoint are executed once again. A checkpoint is established by copying the contents of primary memory (which can be affected by failures) into some secondary memory device (disk or tape). After a failure, and before all the transactions on the audit trail can be re-executed, the contents of the checkpoint have to be copied back into primary memory. In [Gelenbe 76a], this system has been modelled as a queue whose server can be in one of three states: the server state is controlled by a Markov chain. In [Gelenbe 76b] the case of multiple types of failures and checkpoints has been considered. [Young 74], [Kovalenko 74], [Chandy 75a, b] present models of roll-back recovery in which the queueing delay and the backlog of transaction requests is not taken into account. They assume a constant checkpoint interval and obtain its optimum value, i.e. the value which maximizes system availability. In [Chandy 75a, b] the failure rate is assumed to be small. [Robin 77] considers a problem of optimum control based upon the model studied in the present paper.

A similar model arises in reliability studies. Consider a server which goes through maintenance at predetermined instants of time, and which is subject to failures. Suppose that during maintenance periods and while failures are being repaired, the server cannot serve customers. We assume that the time necessary to repair a failure is a function of the age of the failure with respect to the most recent maintenance epoch. Also suppose that customers are served in their order of arrival. This is precisely the model which is being considered in this paper.

The formulation of our problem is contained in Sections 2, 3. The model corresponds to a queue with Poisson arrivals and exponential service times. Maintenance epochs (the checkpoints) are represented by a renewal process. Failures occur at instants described by a Poisson process independent of the arrivals, services and of maintenances. Repairs take an amount of time which is a function of the age of the failure with respect to the most recent maintenance. Service is interrupted during
maintenance and repair.

## 2 - The roll-back recovery process

The service rendered to customers depends on the "state" of the server $X_t$, $t \ge 0$, which is

$$ (2.1) \qquad X_t = \begin{cases} 2 & \text{if the system is creating a checkpoint} \\ 1 & \text{if it is recovering from a failure} \\ 0 & \text{if it is operating normally} \end{cases} $$

Service to requests for transaction processing is rendered only in state 0.

$\{X_t, t \ge 0\}$ is a stochastic point process with the following properties:

(i) The total time spent in state 0 between two consecutive transitions to state 2 is a random variable independent of the past history of the process with general distribution function $F(y)$ and density $f(y)$. That is, during this time the server is available for serving customers which are in queue. Let $E Y = \int_{0}^{\infty} ydF(y) < \infty$.

(ii) When the process enters state 2 it remains there for a random epoch, independent of past history, of general distribution function $C(y)$. At the end of this time it returns to state 0. This is the time it takes to create a checkpoint. We suppose that $E \Delta = \int_{0}^{\infty} ydC(y) < \infty$.

(iii) During epochs when the system is in state 0, instants of transition to state 1 are defined by a Poisson process of parameter $\gamma$. $\gamma$ is the failure rate of the server.

(iv) When a transition into state 1 occurs, the time spent by the server in that state until its return to state 0 is defined as follows. Let $h: \mathbb{R}^{+} \to \mathbb{R}^{+}$ be a measurable function. For a failure (transition from state 0 to 1) taking place at time $t$, let

$$ t' = \sup\{\sigma : \sigma < t \text{ and } 1_2(\sigma) = 1\} $$

Let the random variable $Y_t$ be defined by

$$ (2.2) \qquad Y_t = \begin{cases} \int_{t'}^{t} 1_{0}(\tau) d\tau & \text{if } X_t = 0 \text{ or } 1 \\ 0 & \text{otherwise} \end{cases} $$

That is, $Y_t$ is the total time spent by the server in state 0 in the interval $[t', t]$ where $t'$ is the most recent time before $t$ at which the server was in state 2. Then the server remains in state 1 (after a failure which occurred at time $t$) for a time of duration $h(Y_t)$.
Thus the recovery time of the server is a function of the age $Y_t$ of the server with respect to the most recent checkpoint.

Formally speaking, let $(\Omega, A, \mathcal{F})$ be a probability space, and let $X_n, T_n, n \in \mathbb{N}$, be random variables defined on such that

$$X_n = \Omega \to \mathcal{F}, T_n : \Omega \to \mathbb{R}^+, T_n \le T_{n+1}$$

where $\mathcal{F}$ is a finite set. Then for all $j \in \mathcal{F}, n \in \mathbb{N}, t \in \mathbb{R}^+$ we assume that

$$ (2.3) \qquad \begin{aligned} P[X_{n+1} = j, T_{n+1} - T_n \le t | X_i, T_i, 0 \le i \le n] \\ &= P[X_{n+1} = j, T_{n+1} - T_n \le t | X_n, T_n - T_{n-1}] \\ &\ne P[X_{n+1} = j, T_{n+1} - T_n \le t | X_n] \end{aligned} $$

The process $(X, T)$ is clearly not a Markov-renewal process [Cinlar 76] because of the above non-equality.

Consider now the random variable

$$A_n = T_n - T_{n-1}, n \ge 0$$

and the process $\{X_n, \hat{A}_n, T_n, n \ge 1\}$; it may be viewed as a Markov renewal process with state space $\mathcal{F} \times \mathbb{R}^+$. We associate with it the process $(X, \hat{A}) = \{X_t, \hat{A}_t, t \ge 0\}$ such that

$$X_t = X_n \quad \text{for } t \in [T_{n-1}, T_n[$$

$$\hat{A}_t = t - T_n \quad \text{for } t \in [T_{n-1}, T_n[$$

The queueing system we analyze in the following section is controlled by a process of the form $(X, \hat{A})$.

Returning now more specifically to the stochastic process $(X) = \{X_t, t \ge 0\}$ defined by (1), (i) to (iv), and (2), we are interested in the stationary (equilibrium) probabilities associated with it:

$$\Pi_j \triangleq \lim_{t \to \infty} \Pr[X_t = j], j = 0, 1, 2$$

Since the process is not Markovian, or Markov renewal, we cannot call upon classical results in order to obtain them. We can, however, proceed using an elementary approach.

For $t \ge 0$, define
$$Z_t = \begin{cases} 1 & \text{if } X_t \in \{0, 1\}, \quad t \ge 0 \\ 0 & \text{otherwise} \end{cases}$$

and notice that

$$\mathrm{Pr}[X_t = 1] = \mathrm{Pr}[X_t = 1 | Z_t = 1] \mathrm{Pr}[Z_t = 1]$$

(Z) $\triangleq \{Z_t, t \ge 0\}$ is an alternating renewal process. Therefore we can use its properties to compute $\Pi_0$.

Consider an epoch between two successive checkpoints such that the total time spent in state $X_t = 0$ is $y$. Since failures occur according to a Poisson process, conditioned on $n$ occurrences of failures the instants of occurrence of the $n$ failures are independent and each is uniformly distributed of density $1/y$ in the interval $[0, y]$. This follows from well-known properties of the Poisson process (cf. [Cox 66], pp. 27-28). Thus the expected value of the total time spent in state 1 of (Z) is

$$y + \sum_{n=0}^{\infty} n \left(\frac{\gamma y}{n!}\right)^n e^{-\gamma y} \int_{0}^{y} \left(\frac{h(x)}{y}\right) dx = y \left[1 + \gamma \int_{0}^{y} \left(\frac{h(x)}{y}\right) dx\right]$$

for given $y$, and its expectation over all values of $y$ is

$$(2.4) \qquad EY + \gamma \int_{0}^{\infty} dF(y) \int_{0}^{y} h(x) dx$$

and therefore

$$(2.5) \qquad \lim_{t \to \infty} \mathrm{Pr}[Z_t = 1] = \frac{\mathrm{EY} + \gamma \int_0^\infty dF(y) \int_0^y h(x) dx}{\mathrm{EC} + \mathrm{EY} + \gamma \int_0^\infty dF(y) \int_0^y h(x) dx}$$

using a standard result for alternating renewal processes. [Cox 62].

Notice that

$$\Pi_0 = \lim_{t \to \infty} \mathrm{Pr}[X_t = 0 | X_t = 0 \text{ v } 1] \cdot \lim_{t \to \infty} \mathrm{Pr}[Z_t = 1]$$

It is derived using an argument for which I am indebted to I. NITRANI. Let $a(x)$ be the probability density function of the total time between successive checkpoints, and let $b(x)$ the expectation of total time during which the state of the server is 0 in an interval between two successive checkpoints given that the length $\ell$ of this interval is $x$. Given $x$, notice (using the properties of the "random observer", see for instance [Taka 62] pp. 10-11) that

$$\lim_{t \to \infty} \mathrm{Pr}[X_t = 0 | X_t = 0 \text{ v } 1, \ell = x] = \frac{b(x)}{x}$$
because the instant t will be uniformly distributed in the interval [0, x].

$$ \Pi_0 = \int_0^\infty \frac{b(x)}{x} \cdot \frac{xa(x) \, dx}{\int_0^\infty xa(x) \, dx} = \frac{\int_0^\infty b(x) a(x) \, dx}{\int_0^\infty xa(x) \, dx} $$

because $[xa(x)dx/\int_0^\infty xa(x)dx]$ is the probability that the random observer falls within an interval of length $\approx x$ (again using [Takacs 62] pp. 10-11). But

$$ \int_0^\infty b(x)a(x)dx = EY $$

The expected value of the total time spent in state 0 between two successive checkpoints $\int_0^\infty xa(x)dx$ is given by (2.4). Therefore we have

**Theorem 1** : The stationary probabilities associated with $\{X_t, t \ge 0\}$ are

$$ (2.6) \qquad \Pi_0 = EY/(EC + EY + \gamma \int_0^\infty dF(y) \int_0^y h(x)dx) $$

$$ (2.7) \qquad \Pi_1 = \frac{\gamma \int_0^\infty dF(y) \int_0^y h(x)dx}{EC + EY + \gamma \int_0^\infty dF(y) \int_0^y h(x)dx} $$

and $\Pi_2 = 1 - \Pi_0 - \Pi_1$.

Since $\Pi_0$ is the stationary probability that the server is available for service, we shall call it the availability of the server. In the following section, it will reappear in the ergodicity conditions for the queue length process. We write it in the more convenient form :

$$ (2.8) \qquad \Pi_0 = [1 + EC/EY + (\gamma/EY) \int_0^\infty h(y)(1-F(y))dy]^{-1} $$

## 2.1 - The optimum checkpoint interval

Several authors ([Young 74], [Chandy 75a, b], [Gelenbe 76a, b], [Kovalenko 74]) have examined the problem of the choice of the optimum checkpoint interval. Before briefly reviewing previous work let us introduce some definitions.
The checkpoint interval (CI) is the random variable Y defined in (i). It is the total time between two successive checkpoints during which the system is available for processing transactions which have not been processed before, and F(y) is its distribution function.

The total real-time between checkpoints (TRBC) is the total real-time which elapses between two successive checkpoints; it is made up of the CI plus all the intervals of failure recovery. We shall denote it by the random variable $\xi$, and its distribution function will be denoted $\hat{F}(y)$.

[Young 74] and [Chandy 75a, b] assume that the failure rate is very small : $Y E \xi \ll 1$. Thus they compute the value of $E \xi$ which maximizes the availability. [Chandy 75a, b] assumes also that $\xi$ is constant (i.e. deterministic). [Gelenbe 76a] assumes that Y is exponentially distributed and computes the value of $EY$ which maximizes the availability. [Kovalenko 74] assumes that Y is constant.

Here we shall examine (see (2.6)) the choice of $F(y)$ which maximizes the availability $\Pi_0$: this is the general problem of the optimum checkpoint interval. Previous work has been carried out under restrictive assumptions because either $Y$ has been assumed to be very small, or a special form for $F(y)$ has been assumed, or both.

Let $\mathcal{N}(y) \triangleq \int_0^y h(x)dx$, and denote by $\mathfrak{F}_a$ the set of all probability distribution functions of fixed and finite expectation $a \ge 0$. Let $E \mathcal{N}$ be the expectation of $\mathcal{N}(Y)$ if $Y$ is distributed according to some $F \in \mathfrak{F}_a$.

**Remark 2**: If $E \mathcal{N} \ge \mathcal{N}(a)$ then the element of $\mathfrak{F}_a$ which maximizes $\Pi_0$ (for fixed $a \ge 0$) is

$$ U_a(y) = \begin{cases} 1 & \text{if } y \ge a \\ 0 & \text{if } y < a \end{cases} $$

Notice that $E \mathcal{N} \ge \mathcal{N}(a)$ if $\mathcal{N}(y)$ is convex (i.e. $h(y)$ is increasing).

**Proof**: Consider, for fixed a,

$$ \Pi_0 = [1 + EC/a + (\gamma/a) \int_0^\infty dF_a(y) \mathcal{N}(y)]^{-1} \\ = [1 + EC/a + (\gamma/a) E \mathcal{N}]^{-1} $$
Clearly $\int_{0}^{\infty} dU_{a}(y) \mathcal{L}(y) = \mathcal{L}(a)$, completing the proof.

So far we have treated the recovery time as an abstract quantity $h(y)$. As in previous work, we shall take

$$ (2.9) \qquad h(y) = \alpha y + \beta $$

where $\alpha, \beta > 0$ are constants. This form is intuitive in the context of database operation: $\beta$ is a fixed time associated with reloading the information stored at the checkpoint back into primary memory, and $\alpha y$ corresponds to the time necessary to re-execute transactions which were processes in time $y$. We will return to the choice of $\alpha$ at the end of this paper. Notice now that

$$ (2.10) \qquad \mathcal{L}(y) = \frac{\alpha}{2} y^2 + \beta y $$

and

$$ E \mathcal{L} = \frac{\alpha}{2} EY^2 + \beta EY \ge \mathcal{L}(EY) = \frac{\alpha}{2} (EY)^2 + \beta EY $$

Suppose that the probability distribution function of the optimum checkpoint interval $F^*(y)$ is in $\mathfrak{F}_a$ (i.e. $a = \int_{0}^{\infty} ydF^*(y)$) for some $a \ge 0$. Then by the above remark $F^*(y) = U_a(y)$, and

$$ (2.11) \qquad \Pi_{0}(F^{*}(y)) = [1 + EC/a + \gamma \beta + \alpha \gamma a/2]^{-1} $$

Let us now examine the problem of the choice of the parameters $\alpha$ and $\beta$ in (2.9).

Define $p^*(0,0)$ the stationary probability that the system is idle, given that it is in state 0 (normal operation). Then, in a long interval of normal operation of length $y$ the system will be busy during a time of average value $y(1-p^*(0,0))$. Suppose that transactions arrive to the system at a rate $\lambda$, and let $\mu$ be the service rate. Then during the interval of length $y$, the number of transactions processed will be on the average $\mu y(1-p^*(0,0))$. Let $k$ be the proportion of transactions which have to be reprocessed after a failure; if each transaction reprocessing is as long as the transaction processing it is reasonable to suppose that the reprocessing time for a failure which occurs after $y$ time units of normal operation will take, on the average, a time $\mu^{-1}\mu k y(1-p^*(0,0))$. Therefore we shall take
$$ \alpha \approx k(1-p*(0,0)) $$

and

$$ (2.12) \qquad h(y) = ky(1-p*(0,0)) + \beta $$

In Section 3 we shall show rigorously that

$$ p*(0,0) = 1 - \lambda/\mu\Pi_0 $$

Therefore we take

$$ (2.13) \qquad \alpha = k\lambda/\mu\Pi_0 $$

Combining (2.11) and (2.13) we have

$$ (2.14) \qquad \Pi_0 \left[ 1 + \frac{EC}{\dot{a}} + \gamma\beta \right] = 1 - k\gamma a\lambda/2\mu $$

We are now ready to obtain the value $\hat{a}$ of the optimum checkpoint interval from (2.14).

**Result 3** : The value of a which maximizes $\Pi_0$ in (2.14) is :

$$ (2.15) \qquad \hat{a} = \frac{EC}{1 + \beta\gamma} \left[ \sqrt{1 + \frac{2(1 + \beta\gamma)}{\rho\gamma k EC}} - 1 \right] $$

where $\rho = \lambda/\mu$.

The expression (2.15) is our new formula for the optimum checkpoint interval : clearly it is dependent on $\rho$ the load factor of the transaction processing model. The value $\hat{a}$ is quite different from the formula $(2EC/\alpha\gamma)^{1/2}$ for the optimum checkpoint interval derived in [Young 74] and [Chandy 75a] which is not applicable if (2.13) is used for the choice of $\alpha$.

Consider the case when $p*(0,0) \approx 1$ (the system is heavily loaded) and

$$ 2(1 + \beta\gamma)/\rho\gamma k EC \gg 1 $$

Then

$$ \hat{a} \approx \sqrt{\frac{2EC}{\rho\gamma k(1 + \beta\gamma)}} $$
which resembles somewhat the formula provided by [Young 74] and [Chandy 75a]. Another case of interest arises when

$$2(1 + \beta\gamma) \ll \rho\gamma kEC$$

We then have

$$\hat{\alpha} \approx 1/\rho\gamma k$$

The use of (2.12) for the recovery time and of (2.13) has been validated in a series of simulations reported in [Flamand 77]. On Figure 1 we show a sample result. Two simulations are conducted. In the first case (Case 1) the actual number of transactions processed (the contents of the audit trail) is recorded; when a failure occurs the same number of transactions is reprocessed. In Case 2 $p*(0,0)$ is estimated by measuring the proportion of time up to a failure when the server was idle given that it was in state 0; this is then used in (2.12). The simulations show very good agreement between Case 1 and Case 2 for $\Pi_0$, and an acceptable agreement (the confidence intervals cover each other) for the average queue length of transaction requests. In both cases we show the 95% confidence intervals. The theoretical result (using (2.14)) for $\Pi_0$ is also shown. In Section 3 we shall see that we are unable to compute the average queue length exactly.

## 2.2. — The TRBC with the optimum CI

It is of interest to obtain $\hat{F}(y)$, the distribution of the total real-time $\xi$ between checkpoints (TRBC) when the optimum CI is used. From (2.4) we have

$$E\xi = (2EC/\alpha\gamma)^{1/2} (1 + \gamma\beta) + EC$$
$\gamma = 0.01$

$\beta=0$

$EC = 10$

$a = 251$

$\mu = 1$

<figure><img src="image_3.png" /><figcaption>Figure 1</figcaption></figure>
We will derive $\hat{f}*(s) \triangleq \int_{0}^{\infty} e^{-sy} d\hat{F}(y)$. Notice that for constant $\hat{a}$, and given n events in the interval $[0, \hat{a}]$ according to a Poisson process, the n instants of occurrence are independent and uniformly distributed in $[0, \hat{a}]$. Thus the n recovery times are independent; the density function of any one is

$$f_h(y) = \begin{cases} (\alpha \hat{a})^{-1} & \text{if } y \in [\beta, \beta + \hat{a}\alpha] \\ 0 & \text{otherwise} \end{cases}$$

Therefore, if $f_h^*(s) \triangleq \int_0^\infty f_h(y)e^{-sy}dy$

$$\begin{aligned} \hat{f}*(s) &= [e^{-s\hat{a}}] \left[ \sum_{n=0}^{\infty} \frac{(\gamma\hat{a})^n}{n!} e^{-\gamma\hat{a}} (f_h^*(s))^n \right] \\ &= \exp[-s\hat{a} + \gamma\hat{a}(f_h^*(s) - 1)] \end{aligned}$$

where

$$f_h^*(s) = (\hat{a}\alpha s)^{-1} e^{-\beta s} [1 - e^{-\alpha s}]$$

The variance of $\xi$ is obtained as

$$(2.16) \quad E[(\xi - E\xi)^2] = \gamma\hat{a}[\beta^2 + \hat{a}\alpha\beta + (\alpha\hat{a})^2/3]$$

We see that, even for small values of $\gamma$, it can be quite large at the optimum value of the CI.

### 3 - Analysis of the queue

In this section we analyze the queueing process representing the number of transactions awaiting processing and the state of the server. Our purpose is to determine measures of performance such as the utilization of the server (i.e. the steady-state probability that the queue length is not zero), the saturation condition (i.e. the value of the arrival rate $\lambda$ of transaction requests beyond which stationary queue length will be infinite) and the distribution of the number of customers in queue. This queueing analysis is new. Of interest to us is the stochastic process
$(N, X, Y) \triangleq \{N_t, X_t, Y_t, t \ge 0\}$ where $N_t$ and $X_t$ are the number of customers in queue and the state of the server, respectively, at time $t$; $Y_t$ is defined in (2.2).

Intuitively speaking, the random variable $Y_t$ allows us to compute the amount of time $h(Y_t)$ which is necessary for recovery from a failure which occurs at time $t$ when the server is in state 0.

The analysis of the queueing system is undertaken under the following assumptions. Requests for transactions arrive according to a Poisson process of parameter $\lambda$, and are served in first-come-first-served order when the server is in state 0. No service is rendered in states 1 and 2 of the server. The service time distribution for a transaction is exponentially distributed of parameter $\mu$.

Our study begins with the conditional process

$$ (N, Y | X = 0) \triangleq \{N_t, Y_t | X_t = 0, t \ge 0\}. $$

### 3.1 - The conditional process $(N, Y | X = 0)$

Let $p(n, y, t) = P[N_t = n, Y_t = y | X_t = 0]^{1)}$, and let us introduce the following notations :

$$ (3.1) \qquad \eta(y) = f(y)/(1 - F(y)) \\ r_y(j) = \frac{(\lambda h(y))^j}{j!} \exp(-\lambda h(y)), \quad j \ge 0 $$

Clearly $\eta(y)dy$ is the probability that a checkpoint is established in the interval $[t, t + dy]$ given that $X_t = 0$ and $Y_t = y \cdot r_y(j)$ is the probability that $j$ arrivals occur during a recovery from a failure which took place at time $t$ when $X_t = 0$ and $Y_t = y$.

The following equations are obtained in the usual manner. For $y \ge 0$, $n > 0$ :

$$ (3.2) \qquad \left(\frac{\partial}{\partial t} + \frac{\partial}{\partial y}\right) p(n, y, t) = -\left(\lambda + \mu + \eta(y) + \gamma\right) p(n, y, t) \\ \qquad \qquad + \lambda p(n-1, y, t) + \mu p(n+1, y, t) \\ \qquad \qquad + \gamma \sum_{j=0}^{n} r_y(j) p(n-j, y, t) $$

and for $y \ge 0$, $n = 0$ :

$$ (3.3) \qquad \left(\frac{\partial}{\partial t} + \frac{\partial}{\partial y}\right) p(0, y, t) = -\left(\lambda + \eta(y) + \gamma\right) p(0, y, t) \\ \qquad \qquad + \mu p(1, y, t) + \gamma r_y(0) p(0, y, t) $$

<footnote n="1">1) We mean that $p(n, y, t)dy = P[N_t = n, y \le Y_t < y + dy | X_t = 0] \quad \text{at } t \ge 0$.</footnote>
For $y = 0$ we have for $n \ge 0$:

$$ (3.4) \qquad p(n, 0, t) = \int_{0}^{\infty} \sum_{j=0}^{n} c(j) p(n-j, y, t) \eta(y) dy $$

where

$$ (3.5) \qquad c(j) = \int_{0}^{\infty} \frac{(\lambda z)^{j}}{j!} e^{-\lambda z} dC(z) , \quad j \ge 0 $$

is the probability of $j$ arrivals during the establishment of a checkpoint (see (ii) of section 2).

In the sequel we study the stationary probability distribution for the process $(N, Y | X = 0)$.

**Theorem 4** : The stationary solution of (3.2), (3.3). (3.4) exists if and only if
$$ (\lambda/\mu) < [1 + \mathcal{E}C/EY + (\gamma/EY)] \int_{0}^{\infty} h(y) (1 - F(y)) dy ]^{-1} $$

*Proof* : "Only if" part (necessary condition).

Set $(\partial/\partial t) = 0$ in (3.2), (3.3). Let

$$ p^*(n, s) = \int_{0}^{\infty} e^{-sy} p(n, y) dy $$

where we have dropped the dependence on $t$. Denote

$$ G_y(x) = \sum_{0}^{\infty} x^n p(n, y), \quad G^*(s, x) = \int_{0}^{\infty} G_y(x) e^{-sy} dy $$

We obtain for $n > 0$,

$$ (3.6) \qquad \begin{aligned} sp^*(n, s) - p(n, 0) = &-(\lambda + \mu + \gamma)p^*(n, s) + \mu p^*(n+1, s) \\ &+ \lambda p^*(n-1, s) - \int_{0}^{\infty} e^{-sy} \eta(y) p(n, y) dy \\ &+ \sum_{j=0}^{n} \gamma \int_{0}^{\infty} r_{y}(j) p(n-j, y) e^{-sy} dy \end{aligned} $$

$$ \text{and} \quad \begin{aligned} sp^*(0, s) - p(0, 0) = &-(\lambda+\gamma) p^*(0, s) + \mu p^*(1, s) \\ &- \int_{0}^{\infty} \eta(y) e^{-sy} p(0, y) dy \\ &+ \gamma \int_{0}^{\infty} r_{y}(0) p(0, y) e^{-sy} dy \end{aligned} $$
yielding

$$
\begin{align*}
(3.7) \quad G^*(s, x) [s + \lambda(1-x) + \mu(1 - 1/x) + \gamma] - G_0(x) & \\
&= p^*(0, s) \mu(1 - 1/x) + \gamma H^*(s, x) \\
&\quad - \int_0^\infty \eta(y) G_y(x) e^{-sy} dy
\end{align*}
$$

where

$$
H^*(s, x) = \int_0^\infty e^{-sy} e^{-\lambda(1-x)} h(y) G_y(x) dy
$$

We use (3.4) to obtain

$$
(3.8) \quad G_0(x) = C^*(\lambda(1-x)) \int_0^\infty \eta(y) G_y(x) dy
$$

where

$$
C^*(\lambda(1-x)) = \int_{0}^{\infty} e^{-\lambda(1-x)} z_{dC}(z)
$$

From (3.7) we remain with

$$
\begin{equation}
\begin{aligned}
(3.9) \quad G^*(s, x) = & \frac{p^*(0, s) \mu(1 - 1/x) - \int_0^\infty \eta(y) G_y(x) e^{-sy} dy + G_0(x)}{s + \lambda(1-x) + \mu(1 - 1/x)} \\
& + \frac{\gamma [H^*(s, x) - G^*(s, x)]}{s + \lambda(1-x) + \mu(1 - 1/x)}
\end{aligned}
\end{equation}
$$

where $G_0(x)$ is given by (3.8). It is clear that if the stationary distribution
${p(n, y), n \ge 0, y \ge 0}$ exists we must have

$$
\lim_{x \to 1} \lim_{s \to 0} G^*(s, x) = 1
$$

Taking the limits in (3.9), we have an indeterminate form in both terms
on the right-hand side. Therefore take first

$$
\begin{equation}
\begin{split}
(3.10) \quad \lim_{s \to 0} G^*(s, x) = & \frac{p^*(0, 0) \mu(1 - 1/x) + [C^*(\lambda(x-1)) - 1] \int_0^\infty \eta(y) G_y(x) dy}{\lambda(1-x) + \mu(1 - 1/x)} \\
& - \frac{\gamma [H^*(0, x) - G^*(0, x)]}{\lambda(1-x) + \mu(1 - 1/x)}
\end{split}
\end{equation}
$$

and now apply 1'Hôpital's rule using

$$
\lim_{x \to 1} \frac{d}{dx} C^*(\lambda(1-x)) = \lambda E C
$$
$$ \lim_{x \to 1} C^*(\lambda(1-x)) = 1 $$

$$ \lim_{x \to 1} \frac{d}{dx} H^*(0, x) = \lim_{x \to 1} \frac{d}{dx} G^*(0, x) + \int_{0}^{\infty} \lambda h(y) G_{y}(1) dy $$

so that

$$ (3.11) \quad \lim_{x \to 1} \lim_{s \to 0} G^*(s, x) = \frac{\mu p^*(0, s) + \lambda EC \int_{0}^{\infty} \eta(y) G_{y}(1) dy + \lambda \gamma \int_{0}^{\infty} h(y) G_{y}(1) dy}{- \lambda + \mu} $$

To complete the proof, we shall call upon the following lemma.

**Lemma 5** : $G_y(1) = \lim_{t \to \infty} \sum_{n=0}^{\infty} p(n, y, t)$ is given by

$$ G_{y}(1) = (1 - F(y))/EY $$

*Proof* : This is again a consequence of the well-known result ([Takacs 62], pp. 10, 11) concerning renewal processes. Write

$$ K(y, t) = \int_{0}^{\infty} p(n, z, t) dz $$

so that

$$ \lim_{t \to \infty} K(y, t) = \int_{0}^{y} G_{z}(1) dz $$

Then

$$ (3.12) \quad K(y, t) = \sum_{k=1}^{\infty} P[t < \sigma_k \le t+y < \sigma_{k+1}] $$

where (since we are dealing with the conditional process $(N, Y | X = 0)$) any instant of time $t$ is relative to epochs during which the state of server is $0$; that is $t$ corresponds to the "real" time $t'$ (in process time of $(N, Y, X)$) where

$$ t = \int_{0}^{t'} 1_{0}(\tau) d\tau $$

In (3.12) $\sigma_1 < \dots < \sigma_k < \sigma_{k+1} < \dots$ are defined by $Y_{\sigma_i} = 0$. Clearly the $(\sigma_{k+1} - \sigma_k)$ are independent and identically distributed of probability distribution function $F(y)$. Thus

$$ (3.13) \quad \lim_{t \to \infty} K(y, t) = \int_{0}^{y} [1 - F(x)] dx/EY $$
and the lemma is established.

Now returning to (3.11) and the proof of Theorem 2, we see that

$$ 
\begin{align*}
\int_0^\infty \eta(y) G_y(1) dy &= \int_0^\infty \left[ \frac{dF(y)}{1-F(y)} \right] \left[ \frac{1-F(y)}{1-F(y)} \right] / EY \\
&= 1/EY
\end{align*}
$$

Therefore

$$ (3.14) \qquad p^*(0, 0) = 1 - \left(\frac{\lambda}{\mu}\right) \left[ \frac{1+EC}{EY} + \gamma \int_0^\infty dyh(y) \frac{(1-F(y))/EY}{1-F(y)} \right] = 1 - \frac{\lambda}{\mu\Pi_0} $$

if the stationary solution to (3.2), (3.3), (3.4) exists. But we must have

$p^*(0, 0) = \int_0^\infty p(0, y)dy > 0$, completing the first part of the proof.

### "If" part (sufficient condition)

To prove that the condition is sufficient consider the instants $\sigma_i^+$ just after the instants $\sigma_i$ when $Y_{\sigma_i} = 0$ in the process time of $(N, Y | X = 0)$. The process

$$ (\hat{N} | X = 0) \equiv \{ N_{\sigma_i^+}, i \ge 1 \mid X_t = 0, t \ge 0 \} $$

is a discrete time Markov chain, and it is easy to see that it is aperiodic and irreducible. We first prove that is ergodic under the condition of the Theorem by applying a lemma of [Pakes 69] which we recall below.

**Lemma** : Let $\{B_i, i \ge 1\}$ be an aperiodic irreducible Markov chain. It is ergodic if the following conditions are satisfied :

$$ |E[B_{i+1} - B_i | B_i - j]| < \infty \text{ for all } j $$

$$ \limsup_{j \to \infty} E[B_{i+1} - B_i | B_i = j] < 0 $$

Let $\alpha = \sigma_{i+1}^+ - \sigma_i^+$; in the sequel all events are conditioned on $N_{\sigma_i^+} = j$.

Let $T$ be the total time in the interval $[\sigma_i^+, \sigma_{i+1}^+[$ during which the queue is non-empty. Clearly $T \le \alpha$. Let $D(\alpha)$ be the number of departures from the queue in the interval $[\sigma_i^+, \sigma_{i+1}^+[$.

$$ 1 \ge P[T = \alpha] \ge P[D(\alpha) < j] $$

$$ \text{But} \quad P[D(\alpha) < j] \ge \int_0^\infty dF(\tau) \sum_0^{j-1} \left(\frac{\mu\tau}{\ell!}\right)^\ell e^{-\mu\tau} $$
since the event $[D(\alpha) < j]$ implies the event $[(\text{the number of departures in a busy period of length } \alpha) < j]$. Therefore

$$ (3.15) \qquad \lim_{j \to \infty} P[T = \alpha] = 1 $$

Now consider

$$ E[N_{\sigma_{i+1}^{+}} - N_{\sigma_{i}^{+}} | N_{\sigma_{i}^{+}} = j] = E[D(\alpha) - A(\alpha)] $$

where $A(\alpha)$ is the number of arrivals in $[\sigma_i^+, \sigma_{i+1}^+]$. Clearly

$$ E[A(\alpha)] = \lambda[EY + EC + \gamma \int_{0}^{\infty} h(y)(1 - F(y))dy $$

Also $E[D(\alpha)] = \mu E[T]$; however

$$ \lim_{j \to \infty} E[T] = EY $$

Therefore, if the condition of the Theorem is satisfied then both conditions of Pakes' Lemma are satisfied by $(\hat{N}|X=0)$ so that this Markov chain is ergodic.
It is easily seen that $p(n, y)$ also exists.

As an immediate consequence we have

**Theorem 6** : Under the conditions of Theorem 4, the stationary probability distribution for the process $(N | X = 0)$ exists and its generating function

$$ G(x) \triangleq \lim_{s \to 0} G^*(s, x) \text{ satisfies :} \\ G(x) = \frac{\gamma H^*(0, x) + p^*(0, 0)\mu(1 - 1/x) + (c^*(\lambda(x-1)) - 1) \int_0^\infty \eta(y)G_y(x)dy}{\gamma + \lambda(1 - x) + \mu(1 - 1/x)} $$

## 3.2 - The process $(N)$

Let the (unconditional) queue length process be denoted $(N) \triangleq \{N_t, t \ge 0\}$.

In this section we extend the results of Sections 2 and 3.1 to $(N)$. The remaining work is largely technical.

Let us introduce the following notations for $t \ge 0$ :

$$ a(n, u, t) \triangleq P[N_t = n, U_t = u, X_t = 2] $$

where for $X_t = 2$ :
$$t - U_t \triangleq \sup\{\tau = \tau < t \wedge X_\tau = 0\}$$

$$b(n, y, v, t) = \begin{cases} 0 & \text{if } v > h(y) \\ P[N_t = n, Y_t = y, V_t = v, X_t = 1], & \text{otherwise} \end{cases}$$

where for $X_t = 1$ :

$$t - V_t \triangleq \sup\{\tau : \tau < t \wedge X_\tau = 0\}$$

Let $a(n, u)$, $b(n, y, v)$ be the corresponding quantities obtained by taking $\lim_{t \to \infty}$, if they exist.

$$\text{Remark 1 : } a(n, u) = \Pi_0 \left(1 - C(u)\right) \sum_{j=0}^{n} \frac{(\lambda u)^j}{j!} e^{-\lambda u} \int_0^\infty p(n-j, y) \eta(y) dy$$

$$\text{Remark 2 : } b(n, y, v) = \Pi_0 \gamma \sum_{j=0}^{n} \frac{(\lambda v)^j}{j!} e^{-\lambda v} p(n-j, y)$$

**Theorem 7 :** $a(n, u)$, $b(n, y, v)$ exist for all $n \ge 0$, $y \ge 0$ and $y \ge 0$ such that $0 \le v \le h(y)$, if and only if $p(n, y)$ exists for all $n \ge 0$, $y \ge 0$.

# 4 - Conclusions

In this paper we give a detailed theoretical treatment of the problem of determining the optimum checkpoint interval, i.e. the total time between successive checkpoints during which the data-base system is not recovering from failures, which maximizes system availability.

We first obtain, under some general assumptions, the expression for the availability. We then show that the optimum checkpoint interval must be **deterministic** and that **it is a function of the system load**. An explicit expression for its value is given. These are the main practical contributions of the paper.

These results of practical interest are obtained by means of a theoretical analysis of a queueing system representing system behaviour. This queue has failures and repair times which are a function of the age of the failure with respect to the most recent maintenance (checkpoint) epoch. The queueing model appears to be novel and may have applications to other reliability studies.
REFERENCES

[Cox 62] D.R. Cox - "Renewal Theory" - Methuen - London - 1962.

[Takacs 62] L. Takacs - "Introduction to the Theory of Queues" - Oxford University Press - New York - 1962.

[Loynes 62] R.M. Loynes - "The stability of a queue with non-independent inter-arrival and service times" - Proc. Cambridge Philos. Soc. 58 - 497-520 - 1962.

[Cox 66] D.R. Cox, P.A.W. Lewis - "The Statistical Analysis of Series of Events" - Methuen - London - 1966.

[Pakes 69] A.G. Pakes - "Some conditions for ergodicity and recurrence of Markov chains" - Operations Research 17, 1058-1061 - 1969.

[Young 74] J.W. Young - "A first-order approximation to the optimum checkpoint interval" - CACM 17, 9 - 530-531 - September 1974.

[Kovalenko 74] I.N. Kovalenko, L.S. Stoikova - "On the productivity of a system and the problem solving time in the presence of random failures and aperiodic memorization of the results" - Translated from Kibernetic n°5 - 73-75 - September-October 1974 - Cybernetics Plemum Publishing Corp. - New York - 1976.

[Cunlar 75] E. Cunlar - "Introduction to Stochastic Processes" - Prentice Hall - New York - 1975.

[Chandy 75a] K.M. Chandy, J.C. Browne, C.W. Dissly, W.R. Uhrig - "Analytical Models for Roll back and Recovery Strategies in Data Base Systems" - IEEE Transactions on Software Engineering - Vol. 1, n° 1, - pp. 100-110 - March 1975.

[Chandy 75b] K.M. Chandy - "A survey of analytic models of roll-back and recovery strategies" - IEEE Computer 8, n° 5 - 40-47 - 1975.

[Borovkov 76] A.A. Borovkov - "Stochastic Processes in Queueing Theory" - Springer - New York - 1976

[Gelenbe 76a] E. Gelenbe, D. Derochette - "On the stochastic behaviour of a computer system under Intermittent failures" - in Modelling and Performance Evaluation of Computer Systems - H. Beilner and E. Gelenbe eds. - North-Holland - 1976.

[Gelenbe 76b] E. Gelenbe - "On roll-back recovery with multiple checkpoints" - Proc. 2nd International Symposium on Software Engineering (IEEE Press) - San Francisco - Oct. 1976.

[Robin 77] M. Robin - To appear.

[Flamand 77] J. Flamand, E. Gelenbe - "Simulation of roll-back recovery in a database system" - To appear.