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

HAL
open science

# Existence and uniqueness of stationary distributions in a model of roll-back recovery

Erol Gelenbe

► To cite this version:

Erol Gelenbe. Existence and uniqueness of stationary distributions in a model of roll-back recovery. [Research Report] IRIA-RR-212, IRIA. 1977, pp.14. hal-04716434

HAL Id: hal-04716434

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

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
IRIA
laboria

laboratoire de recherche
en informatique
et automatique

EXISTENCE AND UNIQUENESS
OF STATIONARY DISTRIBUTIONS
IN A MODEL
OF ROLL-BACK RECOVERY

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

Erol GELENBE

Rapport de Recherche N° 212

Janvier 1977

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20
EXISTENCE AND UNIQUENESS OF STATIONARY DISTRIBUTIONS
IN A MODEL OF ROLL-BACK RECOVERY

E. Gelenbe

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. A condition on the traffic intensity of transaction requests is established which insures that the system will not saturate. This condition is essential if meaningful simulation studies of these complex systems are to be conducted. In probabilistic terms, this is the necessary and sufficient condition for the existence of the stationary probability distribution associated with the non-Markovian queueing process representing the backlog of requests to the computer system. Expressions are obtained for the availability of the system and for the stationary probability that the system is idle. 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é :

Un modèle mathématique des procédures de reprise sur erreur est présenté pour un système in-
formatique interactif (système de réservation, système de fichier, etc . . . ). La file des transac-
tions en attente de service est représentée de façon explicite ainsi que le blocage du système au
cours de l'implantation des points de reprise et de la reprise après une erreur. Les conditions
nécessaires et suffisantes d'ergodicité (stabilité) du modèle sont établies. Le taux de disponibilité
du système ainsi que son taux d'activité à l'état stationnaire sont calculés. Le modèle mathéma-
tique que nous étudions permet aussi d'aborder une classe de files d'attente avec pannes et main-
tenances.
# 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 (which can be affected by failures) into some safe 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. [Chandy 75] presents a survey of earlier work on the subject : in particular, a simple model which does not take into account the queueing delays is used to optimize the availability of the system. In [Robin 77] an optimization problem related to our model is considered. The main optimization problem in this context is the optimal placement of the checkpoints. It is clear that the time necessary for recovery from a failure will depend on the time separating the instant of failure from the most recent checkpoint, and in particular on the total number of transactions processed in this interval.

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 \triangleq \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 \triangleq \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, P)$ be a probability space, and let $X_n, T_n$, $n \in N$, be random variables defined on such that

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

where $F$ is a finite set. Then for all $j \in F$, $n \in 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 [Çınlar 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, Z_n, T_n, n \ge 1\}$; it may be viewed as a Markov renewal process with state space $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 proper-
ties 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 :
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\gamma}{n!}\right)^n e^{-\gamma\gamma} \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) \quad EY + \gamma \int_0^\infty dy f(y) \int_0^y h(x) \, dx
$$

and therefore

$$
(2.5) \quad \lim_{t \to \infty} \Pr[Z_t = 1] = \frac{EY + \gamma \int_0^\infty dy f(y) \int_0^y h(x) dx}{EC + EY + \gamma \int_0^\infty dy f(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} \Pr[X_t = 0 | X_t = 0 \text{ v } 1] \cdot \lim_{t \to \infty} \Pr[Z_t = 1]
$$

It is derived using an argument for which I am indebted to I. MITRANI.
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 for the
server is 0 in an interval between two successive checkpoints given that the length
$L$ of this interval is $x$. Given $x$, notice (using the properties of the "random obser-
ver", see for instance [Takacs 62] pp. 10-11) that

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

$$ \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 check-points $\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 dyf(y) \int_0^y h(x)dx) $$

$$ (2.7) \qquad \Pi_1 = \frac{\gamma \int_0^\infty dyf(y) \int_0^y h(x)dx}{EC + EY + \gamma \int_0^\infty dyf(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} $$

### 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. 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!} \quad \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} d_c(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 2** : The stationary solution of (3.2), (3.3). (3.4) exists if and only if
$$ (\lambda/\mu) < [1 + EC/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) \left[s + \lambda(1-x) + \mu(1 - 1/x) + \gamma\right] - 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

$$
(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)} \\
\qquad + \frac{\gamma[H^*(s, x) - G^*(s, x)]}{s + \lambda(1-x) + \mu(1 - 1/x)}
$$

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

$$
(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)} \\
\qquad + \frac{\gamma[H^*(0, x) - G^*(0, x)]}{\lambda(1-x) + \mu(1 - 1/x)}
$$

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 E C \int_0^\infty \eta(y) G_y(1) dy + \lambda Y \int_0^\infty h(y) G_y(1) dy}{-\lambda + \mu} $$

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

**Lemma 3** : $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 $$
REFERENCES

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

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

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

[Çınlar 75] E. Çınlar - "Introduction to Stochastic Processes" - Prentice Hall - New York - 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.

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

[Robin 77] M. Robin - To appear.

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

[Flamand 76] J. Flamand, E. Gelenbe - "Simulation of roll-back recovery in a database system" - To appear.
$$t - U_t \triangleq \sup\{\tau = \tau < t \mid X_\tau = 0\}$$

$$0 \text{ if } v > h(y)$$

$$b(n, y, v, t) =$$

$$P[N_t = n, Y_t = y, V_t = v, X_t = 1], \text{ otherwise}$$

where for $X_t = 1$ :

$$t - V_t \triangleq \sup\{\tau : \tau < t \mid 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.

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

**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 5** : $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 - Conclusion

In this paper we have considered a complex queueing model encountered in reliability theory and in the modelling of roll-back recovery procedures in computer systems. Necessary and sufficient conditions have been established for the existence of the stationary probability distribution of the model.

A complete analytical solution of the model is probably impossible to obtain in the general case. Therefore this condition is of particular interest if a study of this model via simulation is to be conducted, because a simulation study of the non-stationary system would be very costly to conduct.

The condition derived in this paper has been used in the simulation experiments reported in [Flamand 76].
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) \quad \limsup_{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 \mu \int_{0}^{\infty} h(y)(1 - F(y))dy $$

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

$$ \limsup_{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. Let $\{\Pi_n, n \ge 0\}$ be the stationary probability distribution associated with this chain, which has just been shown to exist. It is easily seen that $p(n, y)$ also exists.

As an immediate consequence we have

**Theorem 4** : Under the conditions of Theorem 2, 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$ :
and the lemma is established.

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

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

Therefore

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

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, \text{ completing the first 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 F[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} $$