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

HAL
open science

# On the stochastic behaviour of a computer system under intermittent failures

Erol Gelenbe, D. Derochette

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

## To cite this version:

Erol Gelenbe, D. Derochette. On the stochastic behaviour of a computer system under intermittent failures. [Research Report] IRIA-RR-160, IRIA. 1976, pp.15. hal-04716388

HAL Id: hal-04716388

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

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_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
IRIA
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

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

ON THE STOCHASTIC BEHAVIOUR
OF A COMPUTER SYSTEM
UNDER INTERMITTENT FAILURES

E. Gelenbe, D. Derochette

Rapport de Recherche N° 160

Mars 1976
ON THE STOCHASTIC BEHAVIOUR OF A COMPUTER SYSTEM
UNDER INTERMITTENT FAILURES

E. Gelenbe*, D. Derochette**

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

Résumé :

Nous étudions le comportement d'un système informatique soumis à des défaillances aléatoires. La méthode des points de reprise est utilisée, comme dans certains systèmes de bases de données, pour assurer le fonctionnement fiable. Un modèle probabiliste nous permet de calculer la disponibilité du système, le taux de charge utile qu'il peut supporter pour un taux de défaillances donné, et son temps de réponse.

Abstract :

A mathematical model of a transaction oriented system under intermittent failures is proposed.
The system is assumed to operate with a check-pointing and roll-back/recovery method to insure
reliable information processing. The model is used to derive the principal performance measures,
including availability, response time and the system saturation point.

<footnote>* IRIA/LABORIA, B.P. 5 - 78150 Le Chesnay (France)</footnote>

<footnote>** Projet de Base de Données Médicale, Faculté de Médecine, Université de Liège (Belgique)</footnote>
# 1. Introduction

The purpose of this paper is to study the performance of a transaction oriented computer system under the effect of intermittent system failures when the roll-back/recovery method is used to maintain the integrity of the data stored in the system. In particular we would like to respond to questions such as "What is the maximum load of transactions the system can support in the presence of a given rate of failure ?" and "How will the response time vary as a function of the failure rate ?", or "What proportion of the system time will be taken up by recovering from failures or preparing check-points as opposed to useful transaction processing ?". All of these questions are particularly important in data-base systems in which elaborate procedures for assuring data integrity can consume an important part of system time, especially during activity periods when the failure rate is high (e.g. when a modified version or a new release of the system is being introduced, or when the data-base contents are being modified frequently and errors are being introduced inadvertently). Here by a *failure* we shall mean not just a deficiency in the hardware or software which leads to erroneous system operation but also the intentional or unintentional introduction of erroneous information which breaches the integrity of the information stored in the system.

The system will be assumed to operate in the standard checkpoint-rollback-recovery (CRR) mode. For the purposes of this paper, the instant of occurrence of a failure will coincide with the instant of detection of a failure ; as we shall presently see, this assumption leads to no loss of generality in our context. CRR mode operation may be described as follows (see Figure 1). At specified instants of time $\{a_i\}_{i \in N^+}$, a checkpoint (CP) is instaured ; that is, a secure and valid copy of all the information contained in the system is stored into a memory unit which cannot be tampered with by failures. The creation of the i-th CP immobilizes the system during $z_i$ seconds.
This means that during the time interval $(a_i, a_i+z_i)$ no transactions can be processed. We also assume here that in this interval no failures can occur; this assumption is not essential and will be removed later. At instants $\{b_i\}_{i \in N^+}$ requests for transactions occur ; we assume that two or more transactions cannot be processed in parallel and that they occur singly (i.e. several transactions cannot be requested simultaneously at some $b_i$). The service time for the i-th transaction is $s_i$. At instants $\{c_i\}_{i \in N^+}$ failures take place. A failure is supposed to invalidate all of the information stored in the system, excepting that which has been saved at the CP which precedes the failure ; this is why the preceding remark that the instant of occurrence and of detection of a failure can be assumed to coincide is valid. For all transactions occurring in the time interval $(a_i, a_{i+1})$ a copy is maintained in the system so that if a failure occurs at some time $t \in (a_i+z_i, a_{i+1})$ all transactions which have occurred in the interval $(a_i+z_i, t)$ have to be processed once again.

CHANDY et al. [1] have obtained analytical results, in particular for the optimal value of the time separating two successive CP's in order to minimize the ratio of total expected down-time (their cost function) to total time over this period. They assume that CP's are established periodically and that failures occur according to a Poisson process. With respect to the statement of the problem they consider, the main difference with our work is that they assume that the transactions which are requested during the establishment of a CP or during roll-back/recovery is negligible, and thus there is no degradation in system performance due to CRR mode operation.

A survey of the work in this area is given by CHANDY [2]. The problem of selecting an optimum CP interval has also been examined by YOUNG [3].

The detailed model and the principal results of this paper will be presented in the following sections. As an example

<footnote n="1">1) In fact we shall presently see that our results will also hold if only a subset of these, e.g. the transactions which modify the contents of the data-base, has to be reprocessed.</footnote>
of the kind of result which we obtain let us mention the following
without giving the detailed assumptions on which it is based.

**Result** Let requests for transactions occur at a fixed rate of $\lambda$ transactions per unit time, and let the average service time for each transaction be $\mu^{-1}$. Let $T$ be the average value of the interval $(a_i+z_i, a_{i+1})$ for any $i$. Denote by $Z$ the average value of $z_i$, and let the time necessary for recovery from a failure by the CRR method be given by $(F + \mu kT)$ on the average. The system will have a finite response time to transactions and be non-saturated if and only if

$$ (1) \qquad \lambda/\mu < (1 + \gamma k \mu T + Z/T + \gamma F)^{-1} $$

where $\gamma$ is the rate of occurrence of failures. $T^\circ$, the value of $T$ which maximizes the supremum of the set of attainable values of $\lambda$ for a non-saturated system is given by

$$ (2) \qquad T^\circ = (Z/\gamma k \mu)^{1/2} $$

In fact (2) which is obtained from (1) immediately is equivalent to a result derived in [1-3].

In the following we shall present a mathematical model of the system we have described. It will turn out to be a non-standard queueing model; that is, one for which the analysis at stationary state is not available in the literature. We shall provide a complete analysis of the model at stationary state giving the generating functions for the relevant probability distributions. The ergodicity condition given in equation (1) will follow from these results.

In order to interpret (1) in the absence of failures and of the CRR mode of operation, one should take $T \to \infty$ and $\gamma \to 0$, with $T\gamma \to 0$. We then obtain the familiar relation $\lambda/\mu < 1$ for avoiding saturation. When the failure rate is small enough to be neglected ($\gamma = 0$), the condition for non-saturation still depends of the frequency with which CP's are established and on the time it takes to establish a CP.
## 2. The mathematical model

In this section we give the assumptions underlying the mathematical model of the system we have described. These assumptions are then used to derive the equations describing the probabilistic state transitions of the system. The main result, giving the necessary and sufficient conditions for non-saturation of the system and the generating functions for the relevant stationary (equilibrium) probability distributions is stated. The results and the main assumptions under which they are derived are interpreted in Section 3. A proof of the results is given in Section 2.3.

It is assumed that requests for transactions and failures occur according to two independent Poisson processes of rates $\lambda$ and $\gamma$, respectively. To be more precise, assume that $a_0 = b_0 = c_0 = 0$, and for all $i \in \mathbb{N}^+$ (the natural numbers) denote $B_i = b_i - b_{i-1}$, $C_i = c_i - c_{i-1}$. Then the $B_i$ and $C_i$ form two sequences of independent and identically distributed exponential r.v. (random variables), respectively of parameter $\lambda$ and $\gamma$. Furthermore $B_i$ is independent of $C_j$ for each $i,j$. In no specific assumption is made concerning the occurrence of transaction requests, except in a section concerning cyclic load patterns, however failures are assumed to occur according to a Poisson process. These assumptions are made for the purpose of mathematical tractability, and also because of unavailability of experimental information which could aid in making a more realistic choice. Experience with probabilistic models in various areas of computer systems does provide guidelines for evaluating the validity of these models' predictions; this point will be discussed in the following section.

We now turn to assumptions concerning the CP intervals. It is assumed that each interval $(a_i, a_i+z_i)$ is a r.v. $Z_i$; the $Z_i$, $i \in \mathbb{N}^+$, are a sequence of independent and identically distributed r.v. Each interval $(a_i+z_i, a_{i+1})$ is a r.v. $A_i$, and the $A_i$ are independent and identically distributed and independent of the $Z_i$. Under these assumptions, the sequence
of instants {$a_i$} U {$a_i+z_i$} forms an alternating renewal process (COX [4]). We shall further assume that $Z_i$ is exponentially distributed with expected value Z, and that $A_i$ is also exponentially distributed with expected value T. The latter assumption differs from that of [1] where each $A_i$ is assumed to be constant.

Suppose a failure occurs at some time $t \in (a_i+z_i, a_{i+1})$. We shall assume that the time for recovery is given by $\mu k (t - a_i - z_i)$, where the distribution of $(t - a_i - z_i)$ will be computed assuming that no failures have occurred between the instants $a_i+z_i$ and t, or more precisely that there are no epochs of roll-back/recovery in that interval. The reason for this assumption is that we are in fact interested in the time during which the system was servicing transaction requests to the exclusion of epochs when it was idle as far as the transactions are concerned. This assumption and the proportionality to $\mu$ and $k$ (some constant) is plausible since the recovery requires the reprocessing of all transactions executed since the last CP. We could have replaced $\mu$ in the expression for the recovery time by $\mu_2$ where $\mu = \mu_1+\mu_2$, and $\mu_1$ is the rate of transactions which do not modify the data-base while $\mu_2$ is the rate of those which do. Alternatively, it is possible to include this distinction between types of transactions in the constant of proportionality $k$. Our assumption here differs somewhat from that in [1]; this point is commented in Section 3. Assuming that no failures occur between $a_i+z_i$ and t, we shall need

$$F_t(x) = \sum_{i=0}^{\infty} \Pr(t-x \le a_i + z_i < t < a_{i+1})$$

which is the cumulative distribution function (cdf) for the time interval separating t from the most recent CP. We may write

$$F_t(x) = \sum_{i=0}^{\infty} \int_{t-x}^{t} \Pr(a_{i+1} - a_i - z_i \ge t-u) \, d. \Pr(a_i + z_i \le u)$$

Notice that the sequence of instants {$a_i+z_i$} forms a renewal process. Therefore for u large (i.e. large t), we have

$$\sum_{i=0}^{\infty} \Pr(a_i + z_i \le u) = u(T+Z)^{-1}$$

since it is the expected number of renewals in time u. Notice also that $\Pr(a_{i+1}-a_i-z_i \ge t-u) = e^{-(t-u)/T}$. We then obtain, after a change of variables, that
$$ (3) \qquad F_t^+(x) = \frac{T}{T+Z} (1 - e^{-x/T}) $$

for sufficiently large t. To obtain the cdf for the time separating t the occurrence of a failure and the most recent CP given that t has occurred before the initiation of the establishment of the next CP (we call this cdf $F_t^+(x)$), it suffices to notice that

$$ F_t^+(x) = F_t(x) / \text{Pr}(t \in (a_i+z_i, a_{i+1}) \text{ for any } i \in \mathbb{N}^+) $$

Using the properties of the alternating renewal process (COX [4]), we have that for large t:

$$ (4) \qquad F_t^+(x) = 1 - e^{-x/T} $$

and the time for recovery from a failure is exponentially distributed of parameter $(\mu kT)^{-1}$.

## 2.1 The state transition equations for the data-base model

The data-base system under CRR mode of operation can be considered as a server providing service to requests for transactions. This server can be in one of three states: the state variable $q = 1$ when the server is available for servicing transactions, $q = 2$ if the data-base is in the process of recovering from a failure and is therefore unavailable for transaction processing which is also the case when $q = 3$ meaning that it is establishing a CP. The system is shown schematically on Figure 2. The state of the data-base system as a whole will be described by the two r.v. $(N_t, Q_t)$ where $N_t$ is the number of transactions waiting to be processed (including the one being processed) and $Q_t$ is the state of the server at time t. For large enough t, so that (3) and (4) are valid, the stochastic process $(N_t, Q_t, t \in \mathbb{R}^+)$ is a continuous time Markov chain. Let $p(n,q,t) = \text{Pr}(N_t=n, Q_t=q)$. The state transition equations for the process are (see the transition rates indicated on Figure 2):
$$
(5) \frac{d}{dt} p(0,1,t) = \mu p(1,1,t) + Z^{-1} p(0,3,t) + (\mu k T)^{-1} p(0,2,t) \\
- (\lambda + \gamma + T^{-1}) p(0,1,t)
$$

$$
(6) \frac{d}{dt} p(n,1,t) = \mu p(n+1,1,t) + Z^{-1} p(n,3,t) + (\mu k T)^{-1} p(n,2,t) \\
+ \lambda p(n-1,1,t) - (\lambda + \gamma + \mu + T^{-1}) p(n,1,t),
$$
$$
\text{for } n \ge 1
$$

$$
(7) \frac{d}{dt} p(0,2,t) = \gamma p(0,1,t) - \left( \lambda + (\mu k T)^{-1} \right) p(0,2,t)
$$

$$
(8) \frac{d}{dt} p(n,2,t) = \gamma p(n,1,t) + \lambda p(n-1,2,t) - (\lambda + (\mu k T)^{-1}) p(n,2,t), \\
\text{for } n \ge 1
$$

$$
(9) \frac{d}{dt} p(0,3,t) = T^{-1} p(0,1,t) - (\lambda + Z^{-1}) p(0,3,t)
$$

$$
(10) \frac{d}{dt} p(n,3,t) = T^{-1} p(n,1,t) + \lambda p(n-1,3,t) - (\lambda + Z^{-1}) p(n,3,t), \\
\text{for } n \ge 1
$$
## 2.2 The main result

From equations (5)-(10) describing the state transitions of the system we shall derive a necessary and sufficient condition for the existence (and, obviously, uniqueness) of the stationary joint probability distribution

$$p(n,q) = \lim_{t \to \infty} \text{Pr}(N_t=n, Q_t=q), \quad n \ge 0, q = 1,2,3.$$

We will also give expressions for the generating functions

$$G_q(x) = \sum_{n=0}^{\infty} p(n,q) x^n, \quad |x| \le 1$$

from which the expected number of transactions waiting for treatment at stationary state, the response time to a transaction request and other statistics of interest can be obtained.

**Theorem 1** The stationary probability distribution for the database system under CRR mode operation exists (i.e. $p(n,q) > 0$ for all $n \ge 0$, $q = 1,2,3$, and $\sum_{q=1}^{3} G_q(1) = 1$) if and only if

$$\rho \stackrel{\text{def}}{=} \lambda/\mu < (1 + \mu kT \gamma + Z/T)^{-1}$$

This result is proved in Section 2.3, where expressions for the generating functions $G_q(x)$, $q=1,2,3$, are also given.

**Theorem 2** Define the availability of the system as the stationary probability that it is in state $q=1$; it is given by

$$A \stackrel{\text{def}}{=} G_1(1) = (1 + \mu kT \gamma + Z/T)^{-1}$$

Theorem 2 is obtained by using (17) in (14) to which is applied 1'Hopital's rule. The response time to a transaction request is defined as the time separating its arrival to the system and the instant of completion; its expected value in stationary state is $W$:

**Theorem 3**

$$W = \frac{\mu^{-1} + A^2 (\gamma(\mu kT)^2 + Z^2/T)}{A - \rho}$$

A proof is given in Section 2.3.
## 2.3 Proof of the main results

The reader uninterested by the proof of Theorems 1 - 3 may skip this section.

From equation (5) - (10), we see that the continuous time Markov chain $(N_t, Q_t, t \in \mathbb{R}^+)$ is aperiodic and irreducible. It is therefore ergodic if and only if a positive solution $p(n,q)$ exists to (5) - (10) in which $\frac{d}{dt} p(n,q,t) = 0, n \ge 0, q = 1,2,3$, such that $\sum_{n=0}^{\infty} p(n,q) < \infty$.

Using (5), (6), we obtain

$$ (11) \quad [\lambda - \lambda x + \gamma + T^{-1} + \mu - \mu/x] G_1(x) = \mu (1 - 1/x) p(0,1) + Z^{-1} G_3(x) + (\mu k T)^{-1} G_2(x) $$

Similarly from (7), (8) and (9), (10) :

$$ (12) \quad \gamma G_1(x) = [\lambda - \lambda x + (\mu k T)^{-1}] G_2(x) $$

$$ (13) \quad T^{-1} G_1(x) = [\lambda - \lambda x + Z^{-1}] G_3(x) $$

These equations yield

$$ (14) \quad G_1(x) = \frac{\mu (1-1/x) p(0,1)}{D(x) - A(x) - B(x)} $$

where

$$ D(x) = \lambda - \lambda x + \gamma + T^{-1} + \mu - \mu/x $$

$$ A(x) = \gamma (\mu k T)^{-1} / (\lambda - \lambda x + (\mu k T)^{-1}) $$

$$ B(x) = Z^{-1} T^{-1} / (\lambda - \lambda x + Z^{-1}) $$

Clearly the system is ergodic only if $p(0,1) > 0$ and $0 < G_1(1) < \infty$.

By applying L'Hôpital's rule to (14), we see that a necessary condition
for ergodicity is that

$$D'(1) - A'(1) - B'(1) > 0$$

or, equivalently that

$$(15) \qquad \mu > \lambda [1 + \mu k T \gamma + Z/T]$$

To show that it is sufficient notice that if $G(x) = G_1(x) + G_2(x) + G_3(x)$, then

$$(16) \qquad G(1) = G_1(1) [1 + \mu k \gamma T + Z/T]$$

Notice also from (5) - (11) with $\frac{d}{dt} p(n,q) = 0$, that if $p(0,1) > 0$, then $p(n,q) > 0$ for all $n \ge 0$, $q = 1,2,3$. Now assume (15) and take

$$(17) \qquad p(0,1) = [1 + \mu k T \gamma + Z/T]^{-1} - \lambda/\mu = A - \rho$$

which is obviously positive. Using (14) to which is applied l'Hôpital's rule in (16) we obtain $G(1) = 1$ which is obviously finite. Therefore (15) is necessary and sufficient for the ergodicity of $(N_t, Q_t, t \in R^+)$ and Theorem 1 is proved.

Let us now turn to the proof of Theorem 3. Using (12) - (14) we write

$$(18) \qquad \begin{aligned} G(x) &= G_1(\pm) + G_2(x) + G_3(x) \\ &= G_1(x) [1 + C(x)] \end{aligned}$$

where

$$C(x) = \frac{\gamma}{\lambda - \lambda x + (\mu k T)^{-1}} + \frac{T^{-1}}{\lambda - \lambda x + Z^{-1}}$$

The expected number of transaction requests in queue in stationary state is

$$E\{N_{\infty}\} = \lim_{x \to 1} \frac{d}{dx} G(x)$$
and by LITTLE'S Theorem, $W = \lambda^{-1} E\{N_{\infty}\}$.

Notice that $C'(1) = A^{-1}$ and

$$C'(1) = \lambda[\gamma (\mu k T)^2 + Z^2/T]$$

Therefore

$$G'(1) = A^{-1} G_1'(1) + A \lambda [\gamma (\mu k T)^2 + Z^2/T]$$

Denote by $u, v$ the numerator and denominator respectively of $G_1(x)$ in (14). Then

$$G_1'(x) = \frac{u'v - v'u}{v^2}$$

which is indeterminate at $x = 1$. L'Hôpital's rule has to be applied to it twice to obtain

$$G_1'(1) = \frac{u''(1)v'(1) - v''(1)u'(1)}{2(v'(1))^2}$$

where

$$u'(1) = \mu (A - \rho), u''(1) = -2 \mu (A - \rho)$$

$$v'(1) = \mu - \lambda A^{-1}, v''(1) = -2\mu - 2\lambda^2(\gamma (\mu k T)^2 + Z^2/T)$$

so that

$$G_1'(1) = \frac{\rho A + \lambda \rho A^2 (\gamma (\mu k T)^2 + Z^2/T)}{A - \rho}$$

and

$$E\{N_{\infty}\} = \frac{\rho + \lambda A^2 (\gamma (\mu k T)^2 + Z^2/T)}{A - \rho}$$

Theorem 3 now follows by applying LITTLE'S formula.
### 3. Generalisations and conclusions

In this section we shall indicate some extensions to our model and draw some conclusions concerning the possible uses of this study.

A difference that the reader will have noticed between our model and those studied in [1-3] is that the average reprocessing time for a roll-back recovery is $\mu$ kT in our model and $\lambda$ kT in theirs. This is due to the fact that in the models of [1-3] there is no queueing delay, therefore the number of transactions processed during an interval is the number which has arrived; in our case the number of transactions processed is proportional to the processing rate. One could argue correctly that for a long enough interval, and provided there is equilibrium, the two rates are the same. In any case, the constant of proportionality k can be used to transform one form of the reprocessing time into the other so that the difference is of little importance.

In reality, the processing time for recovery is proportional to the *actual* number of transactions processed in the interval separating the time when the most recent check-point has been established and the instant at which a failure occurs. This has not been included in our model because of the necessity to include a supplementary variable in the model which complicates considerably the analysis.

One additional aspect that merits analysis is the possibility of including the occurrence of failures during recovery or during the establishment of check-points; suppose that the occurrence of failures during these epochs is governed by the same Poisson process of parameter $\gamma$ as at other times. We shall show that the equations for the model and all of the results remain unchanged. That is, the results derived in the previous sections are still valid without any modifications. This can be shown in two ways: either by deriving the state transition equations (5)-(10) with the new assumptions, or by examining the probability distribution function of an epoch which is obtained by reinitiating an exponentially distributed epoch each time a Poisson event occurs during the epoch. The first
approach is simpler. Consider for instance the derivation of equation (8) if failures can occur during roll-back recovery. Then, for $n \ge 1$,

$$p(n,2,t+\Delta t) = \gamma \Delta t p(n,1,t) + \lambda \Delta t p(n-1,2,t) + \gamma \Delta t p(n,2,t) \\ + (1-(\mu k T)^{-1} \Delta t)(1-\lambda \Delta t)(1-\gamma \Delta t) p(n,2,t)$$

which yields precisely (8) after collecting terms, dividing by $\Delta t$ and letting $\Delta t \to 0$, yields precisely (8). The same thing can be said for (7), (9) and (10). We summarize these remarks in the following theorem.

**Theorem 4.** Theorems 1,2,3 and the generating functions $G_i(x)$, $i=1,2,3$, remain unchanged if we assume that failures can occur during the establishment of check-points or during roll-back recovery.

This result is strongly dependent on the assumptions which govern our model and would not hold if, for instance, the time for recovery were not exponentially distributed.

Our model, and in particular Theorem 3, can be used to provide an estimate for the degradation in performance due to intermittent failures and in particular due to the use of check-pointing and roll-back recovery. Extensions to more general distributional assumptions on service times and check-pointing intervals will yield further insight into the behaviour of computer systems in the presence of failures.
<figure><img src="image_6.png" /><figcaption>Figure 1</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 2</figcaption></figure>
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, No. 1, March 1975, pp. 100-110.

2. K.M. Chandy, "A Survey of Analytic Models of Rollback and Recovery Strategies," *Computer*, Vol. 8, No. 5, May 1975, pp. 40-47.

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

4. D.R. Cox, "Renewal Theory", Methuen, London, 1962.