J. Appl. Prob. 30, 589602 (1993)

Printed in Israel

0 Applied Probability Trust 1993

TRANSIENT BEHAVIOR OF COVERAGE PROCESSES

WITH APPLICATIONS TO THE INFINITESERVER QUEUE

SID BROWNE,* Columbia University

J, MICHAEL STEELE,** University of Pennsylvania

Abstract

We obtain the distribution of the length of a clump in a coverage process where the first line segment of a clump has a distribution that differs from the remaining segments of the clump. This result allows us to provide the distribution of the busy period in an M/G/co queueing system with exceptional first service, and applications are considered. The result also provides the tool necessary to analyze the transient behavior of an ordinary coverage process, namely the depletion time of the ordinary M/G/oo system.

CLUMPS; BUSY PERIODS; DEPLETION TIMES; EXCEPTIONAL FIRST SERVICE

AMS 1991 SUBJECT CLASSIFICATION: PRIMARY 60DOS

SECONDARY 60K25

1. Introduction

If {Si: 1 :_5 i < oo) denotes a sequence of nonnegative random variables, and zi : 1 ~5 i < oc j denotes the points of a homogeneous Poisson process on [0, 00 1 with arrival rate A, the associated coverage process consists of the sequence of halfopen intervals [Ti, cj + S,). The union of this set of intervals can be written uniquely as a set of disjoint halfopen intervals that we call the clumps of the process. The gaps between successive clumps are called spacings.

In the queueing context, S, is the service required by the ith customer, who arrived at time z, to a service facility with an unlimited number of servers (the MIG /00 queue). The clumps are then equivalent to the corresponding busy periods of the system, and the spacings are the idle periods. The clumps also model the dead times in a type 11 counter (see [71, Chapter 2 for further details).

There is an extensive literature for coverage processes where one assumes that all line segment lengths are independent and identically distributed (see [71, Chapter 2), but the

Received 31 January 1992; revision received 5 June 1992.

* Postal address: 402 Uris Hall, Graduate School of Business, Columbia University, New York, NY 10027 USA.

email:sbrowne@research.gsb.columbia.edu

** Postal address: Department of Statistics, The Wharton School, University of Pennsylvania, Philadelphia, PA 19104, USA.

589

i

i

i i i

590 SID BROWNE AND J. MICHAEL STEELE

situation where these properties do not hold has been largely ignored with respect to the clumping aspect (but see [ 141, [41). Here we focus on models that permit the first line segment of each clump to have a distribution that differs from those of the remaining line segments. The resulting exceptional coverage process is quite important in the queueing context, where the clumps would correspond to busy periods in an MIGICC queue where the first customer in every busy period has an exceptional first service requirement. Queueing service systems with this important modification have been studied widely in the literature for the case of a single server (see [51 for a variety of applications and references), but this is the first such study for multiple servers working in parallel. In Section 4 we use our results to analyze a recently proposed model for a database system.

One of the more compelling charms of the exceptional coverage process, though, is that it also gives us an effective tool for studying the transient behavior of ordinary coverage processes. Our main illustration of this principle concerns the determination of the distribution of the socalled depletion time of the ordinary coverage process. Specifically, we consider an ordinary coverage process with independent segment lengths {Si} and common distribution G. For t i> 0 we let X(t) denote the number of segments that cover the point t. For y > 0 we define D (y) to be the distance to the next uncovered point

D(y) = inf {t k_ y: X(t) = 0} y,

and we refer to D(y) as the depletion time at y. In the queueing context, D(y) is the remaining busy period at timeyin an ordinaryMIGloo system. The corresponding result for the single server system is discussed for example in [8].

Theorem 1. The Laplace transform dy(s) = E(exp( sD(y))) is given by

A +X

by (S) = foo exp sx A foy (1 G (u))du} dx

P(S)

wherep(s) = A 1' exp( st)p(t)dt and p(t) = exp{ A S' (1 G(u))du}.

0 0

The stationary regime Laplace transform 3.(s)=limy,,, by(s) follows from our representation of by(s), but &.(s) is really simpler than by(s) and could have been obtained from previously known results. Thus the novelty of the present method rests in the ability to provide information about the genuinely transient case y < 00, rather than the stationary case y = oo.

One can obtain considerable information about D(y) from its transform dy(s), and, although we will collect more detailed information in a later section, we note here that our representation for by(s) gives us the first two moments of the depletion time D(y).

Corollary 1. For the depletion time D (y) of an ordinary coverage process, we have

(2) E(D( exp {A f (1 G(u))du} exp {A f (1 G(u))du dx,

YD = fo X x~, Y

and

Transient behavior of coverage processes 591

Effi'(y)) = 2E(D(y)) f M [exp A f (1 G(u))du} 1] dx

0

(3) +2 C0 X exp A f (1 GGiMu} exp {A f (1 G(u))du dx.

fo 1 x ' _, Y } 1

Modified coverage processes. Our approach to the exceptional coverage process and the depletion time problem call on a loosely related coverage process that is built upon independent random variables {91, S2,. . ., S,,. . . } such that

P(91:5u)=H(u) but P(Si:5u)=G(u) for i k 2.

We call the resulting coverage process the modified coverage process. The key observation is that the length l~l of the first clump in the modified coverage process has a distribution that differs from that of the lengths Bi of all later clumps, yet all of the clumps of the exceptional coverage process have distribution equal to that of & The result that makes this observation effective is the following:

Theorem 2. For ~(s) ~_ E(exp( sA,)) we have ~(s) = 1 Vi(s)1p (s) where

w(s) = A fo"o (1 H(z))exp sz A E (1 G(u))dul dz

and

,u(s) E0 exp sz A fo (1 G(u))du}

The derivation of Theorem 2 as well as some associated results is given in the next section. In Section 3 we return to the depletion time of an ordinary coverage process and prove Theorem 1. In Section 4 we survey the relationship of our results to queueing theory and other fields.

2. Derivation of main results

It is useful to have expressions for the clump length that are valid for all three of the coverage processes studied here. We set WO = 0 and for n k 1 we define

Zn = inf {t W,, X(t) > 0}

and

W, = inf {t > Z, X(t) = 0}.

We see therefore that Z,, corresponds to the end of the nth spacing and Wn corresponds to the end of the nth clump. The variables of central interest here are I, = Z', W,, 1 and Bn = W,, Z, so that I, denotes the length of the nth spacing and B, denotes the length of the nth clump.

2. 1. Distributions for the modified coverage process. Our determination of ~(s) depends on finding two different expressions for the Laplace transform of the clump counting process. We then solve the resulting relationships for the Laplace transform of the clump length.

592 SID BROWNE AND J. MICHAEL STEELE

First expression. Let A~(t) denote the number of clumps started in the interval [0, t I by the modified coverage process. We have A~(0) = 0, and writing the indicator function as 1 we find for t ~i 0 that

A~(t) 1 (1, :5 t } + 1 {I, + fi' + I' t} + 1 {I, + A, + J2 + I, + Bi :5 t} .

n 3 i~3 i~2

We next consider the associated (delayed) renewal measure and its Laplace transform

th(t)=E(Iv~(t)) and P(s)= fo', exp( st)dffi,(t).

We will use the corresponding hatless expressions Bi, M(t), andu(s) in the case G = H. Since the gap length variables Ii are independent and exponentially distributed with parameter A, we have for 6(s) =_ E(exp( sIi)) that 3 (s) = A /(A + s). Since the variables It, A, 12, B2, 13, B35 * ' ' are independent we have

p(S) = J(S) + J2(S)~(S) + JI(S)~(S)#(S) + +.5,(S)~(S),6"1(S) +

and by summing the geometric series we find

P(s) = 3(s) 1 + fl(s)5(s)

1 3(S)#(s)f *

Now, the expression just derived for general G and H remains valid if we set G H, and, in that case, we would have P (s) =p (s) and ~(s) = fl(s) so we find for the ordinary coverage process that we have (see [ 151, [71)

,U(S) = 3(S)/(1 3(S)P(S)).

By using this relationship to clear fl (s) from the preceding general identity for A (s), we find the first of the two required expressions:

Lemma 1. fi(s) = 5(s)f 1 + MSMSM.

Second expression. We obtain our second expression involving ~(s) by exploiting the fact that the process R(t) is a delayed (alternating) renewal process. We first recall that for such a process the delayed renewal measure th (t) = E(A~(t)) has a basic relation to a renewal density given by

P(R(t + dt) R(t) k_ 1) = dth(t) = A0(t)dt

where 0(t) is the probability that t is not covered in the modified clump process. What is needed now is an expression for fi(t) in terms of G and H. An effective one is given in the following result.

Lemma 2. 0(t)= I+AfH(z)exp{.ZfzG(u)du}dz)exp(.At).

0 0

Proof. If we condition on the value of the first Poisson point TI, we find

Transient behavior of coverage processes 593

0) = exp( At) + fo, P(,~(t) = 0 1 c, ~ X)A exp( Ax)dX,

To evaluate P(,~(t) = 0 1 T, = x), we condition on the number N of Poisson points in the interval [x, t]. Given N = n the Poisson points are uniformly distributed in [x, fl, and we find using the exchangeability of the S, for i ~~: 2 that

P(,~(t) = 0 1 r, = x, N = n) = P(S, :5 t x)P max {Si+TJ::StIN=n

( 2 1 i:Sn + 1

~ H(t x)P max (S, + U,} < t

( 2gi:Sn + 1

where the Ui are independent and uniformly distributed on [x, t]. For n = 1 the second factor is just

1 G (t y)dy,

t X X

so in general, we find by the independence of the Si + I, for 2:5 i :5 n + 1 that

P(.,~(t) = 0 1 z, = x, N = n) = H(t y) f t GQ y)dy)n.

x

Finally, we use the fact that N is Poisson with parameter (t x)A and collect terms. The lemma follows after a light computation.

2.2. Completion of the proof 6f Theorem 2. By expressing fi(s) in terms of the renewal density and applying Lemma 2, we find

A(S) fOO exp( st)drh (t) = A foo exp( st),fi(t)dt

A exp( (s + A)t) 1 + A H(z)exp (A f z G (y)dy) dzl dt.

fo"o 1 fo'

After completing the t integration, we find

fi(s)= " (I+AfH(z)exp(sz)p(z)dz),

A + S 0

and when we specialize to the case of H = G we find

P(S) = A f000 exp( sz) p (z)dz.

Finally, on writing H(z) = 1 + (1 H(z)) in our expression for fi(s) we see

fi(s)= A (1+,u(s)Af(1H(z))exp(sz)p(z)dz)

.Z + S 0

8WO + A (S) W(SA

i

i

594 SID BROWNE AND J. MICHAEL STEELE

wherey (s) and Vi(s) are just as specified in the formulas in the statement of Theorem 2. Substituting this into Lemma 2 completes the proof of that theorem.

Our next goal is to use our Laplace transform ~(s) to obtain information about the moments of 1~1. This is provided in the following result.

Corollary 2. Let ~k denote E(A1) for k = 1, 2,. . ., then we have

(4) yi(O)exp(Aa)/A ~ (1 H(z))exp (A (1 G(u))du dz

E

and

(5) 2 exp(A a) W(O) f X (exp A (1 G(u))du) 1) dt w'(0)]

A 0 fo

where a E(S2) (1 G(x))dx is the mean length of an ordinary line segment and

(1 H(x)) p (x)dx

0

and

VIV) A fo', x(l H(x)) p (x)dx.

Proof. First, an application of the Abelian theorem in [ 171, p. 182, shows

lim sy (s) exp( A

S0

since

lim SA exp( st) p(t)dt = A lim p(t) = Ap(co) ~_ A exp( Act).

S0 fo"o t00

Next, we need the following lemma which will also be useful later in obtaining bounds. This can be established by writing W(s) = A S ' ' (1 H(z))exp( sz) p (z)dz and then using the fact that p(z) is continuous and monotonically decreasing (from 1 to exp( A a)) in z.

Lemma 3. Let h(s) denote the Laplace transform of the modified line segment length, i.e. h(s)=E(exp(sgl))~1' exp(sz)dH(z), thenforRe(s)k 0 wehave

0

(6) A exp( Aa) 1 h(s) (S) ;S A 1 h(s)

S S

In particular, if we let 0 = E(,~1) (1 H(z))dz, we have

0

(7) A exp( A affl :_5 V/(0) < AO.

It follows therefore, that since

lim lim

S0 S 30 SIA(S)

Transient behavior of coverage processes 595

we have 01 = yi(O)exp(Aa)/A, which reduces to the form of Equation (4) after some algebraic manipulations.

To establish Equation (5), note first that since

+ O(S)

1 ~(s) = SA 2fl,

we may write

1 + fl2 +00),

fl(S) Sfll 2fl2

and since 1/(1 ~(s)) =,u(s)lqi(s), we have

(8) A(S) + fl2 +0(1).

VI(S) sfll 2fl2

1

The previous lemma shows that Vi(s) admits the expansion (around 0) VI(S) v/(0) +

syil(O) + o(s), and therefore

1 1 W10)

V~ + o (S).

VI(S) W(O) 1(0)

Since o(s)p(s) is o(l) we have

'U(SLMs)S S VIV)

(9) M

+ 00).

~(s ) W(O) (0)

After equating (8) and (9) and rearranging, we find

fl2 (0)

exp( st)[ p (t) exp( A a)ldt su (s) +o(l),

2fl2 W(O)

1 foo

where we used the fact that W(O)exp(Aa)/A. Now let s 0 to obtain the exact

relationship

(10) A = A f p(t) exp( Aa)]dt (0) A exp( A a).

2fl2 W(O)

1 MOW

Upon multiplying both sides by 2~,2~ 2[exp(Aa)w(O)/A12 and using p(t) exp( ,1a) exp( A a)(exp(A 17 (1 G (u))du) 1), we recover (5), thereby completing the proof.

Remark 1. If we let fl2 denote the second moment of the ordinary clump length (i.e. the case when H =_ G), then we find that the second moment of the modified clump is

related to fl2 by ~2 w(O)fl2 W'(0)2 exp(Aa)/A, where (see [161, p. 211)

2 exp(A a) f 00 (exp (A f (1 G (u))du 1 dt.

A 0

i

i i i

596 SID BROWNE AND J. MICHAEL STEELE

Therefore, if we let a' and &' denote, respectively, the variance of an ordinary and modified line segment length, then the condition for ~2 to be finite is that both U2 and &2 be finite. This can be seen by noting that after integrating #2 by parts, we get

,62 = 2 exp(2A a) f t(l G(t))p(t)dt,

and since p (t) is monotonically decreasing, we can bound P2 by (see also [ 101),

exp(A a)(U2 + a 2) _:5 fl2_:5 exp(2A a)(a 1 + a ~.

Now, since we have qi'(0)=11"'t(IH(t))p(t)dt we can bound it by

A exp( Aa)(01 + U2)/2 :_5 V/1(0) 2 + U2 )/2 to get the following bound On fl2:

qi(O)exp(A a)(U2 + a2) + (02 + &2) :_5 j2:_5 exp(,1a)[qi(O)exp(A a)(U2 + a ) + (01 + &~l.

Combining this with our previous bound on Viffi) gives finally

(11) A0(a2 + a 2) + (02 + &2) :5 j2:5 exp(Aa)(A0 exp(A a)(a2 + a ~ + 02 +

Remark 2. The constant Viffi) has the following interesting interpretation: if M(t) denotes the number of ordinary clumps started by time t in the ordinary coverage process, with M(O) = 0, and 9 is an independent random variable with distribution H, then Viffi) = E(M(9)). This means that Viffi) equals the number of ordinary clumps started in an ordinary coverage process in the random interval [0, 9). This follows upon observing that since M(t) has intensity Ap(t), we have

E(M(9)) =E A 9 p (u)du) = A f ( f ' p (u)du) dH(t).

( fo 0 0

Interchanging the order of integration reveals this as Viffi). If we put H = G into the above, we find that the expected number of ordinary clumps that start during an arbitrary line segment length in an ordinary coverage process is in fact the stationary probability of coverage, i.e. when S G we find that E(M(S)) =_ 1 exp( A a). This relationship is of interest in queueing theory because it can be rewritten as

(12) A exp( A a). E(B) = E(M(S)),

where B denotes an ordinary busy period in an M/G/oo queue, with mean E(B)

(exp(Aa) 1)1A. Since Ap(t) A exp( Aa), this states that in an ordinary MIG100 model, the stationary arrival rate of busy periods, times the expected length of a busy period, is equal to the expected number of busy periods that start (arrive) during the service time of an arbitrary customer. (This is somewhat difFerent from the usual implication of Little's law L A W even when the busy periods are viewed as customers in a singleserver queue with a single buffer. See for example [6].)

Remark 3. It seems hopeless to try to invert the transform ~(s) to obtain the explicit distribution of 191 as even the ordinary clump distribution remains intractable in this regard (except for the very special case of constant segment length; see [7], p. 88 and

Transient behavior of coverage processes 597

[ 12]). However, expanding the exponential term in the integrand of Equation (4) shows that A admits the expansion

0 + (1 H(z)) [f (1 G(u))du dz.

E0

Elementary calculations then show that if ordinary line segments are exponentially distributed with mean 0, this reduces to

0 + Y"" (Aa)'a[l h(ila)l

i~1 i! i

If the first line segment is also exponentially distributed with mean a, then this reduces further to

fll=O+Oa i ' i! (a + io)

which has the following representation in terms of the incomplete gamma function y(a, x)~fx exp( t)taldt,

0

fl, = 0 + a[(Aa) "y(alo, Aa) 01a].

3. Applications to depletion times

The key to the derivation of Theorem 1 is that we can show that D(y) has the same distribution as A, in a modified coverage process in which the initial segment length 91 has a special distribution that we can specify in terms of G. This identification then brings the conclusion of Theorem 1 within the reach of Theorem 2.

For y > 0 and all i such that z, z5 y, we introduce new variables Li ~_ zi + Si y, and we call Li the remainingforward length after Y of the ith line segment started before y. If we set T(y) ~_ max{Li (y) ri < y J, we have the following key fact:

Lemma 4. For any y k_ 0, the distribution of D(y) in an ordinary coverage process determined by {S,, S2,. . . is equal to the distribution ofthe length A, ofthefirst clump in a modified coverage process determined by {91, S2, S3,. where 91 is chosen to satisfy P(~l .5 t) P(T(y) :5 t) for all t > 0.

Proof. For i = 1, 2, let {M,(t)} denote independent ordinary coverage processes governed by independent and identically distributed Poisson processes with intensity A, and with the same line segment length distribution G, with Mi(O) = 0 for i = 1, 2. If we let Wi denote the end of the nth clump in the i th coverage process, then a little thought shows that we can write (where we use to denote equality in distribution)

.fl, max{g,, Wm1,(jj,

as well as

D(y) max{T(y), WmI.j(,j.

598 SID BROWNE AND J. MICHAEL STEELE

Ml(t)d

Since M2(t) for every t ~: 0, WmI,(,) Wm,(,) for every t, and the lemma

therefore follows for,~, 1_ T(y).

Completion of the proof of Theorem 1. By this lemma, the required Laplace transform (5,(s) equals ~(s) if S, is chosen to have the same distribution as T(y). To bring this to the explicit level required by Theorem 1, we need to express the distribution of T(y) in terms of G.

P(T(y) :_5 z 1 max (i , Ti y n)

= P(L,(y):5 z for all 1 :_5 i < n 1 maxfi: Ti :_:5 y} n)

= P(,ri + S, :_5 y + z for all 1 < i :_:5 n j max{i: Ti y) = n).

If {Uj: 1 _:5 i _:5 n} denote independent random variables that are uniformly distributed on [0, y], we have

P(Ti + Si :_5 y + z for all 1 :_5 i 5 n 1 max{i: ci :_5 y} = n)

= P(Uj + Si ~_5 y + z for all 1 :_5 i :_5 n).

Since the sums Qi + Si are independent with distribution

' f G(u + z)du,

Y ',

we find the basic conditional probability

P(T(y):_5 z 1 max{i: Ti < y) = n) f Y G(u + Z)dUln. Y ',

Now, since niax{i: Ti :_5 y} has the Poisson distribution with parameter Ay, the law of total probability and a brief calculation give us

P(T(y) ;~ z) = exp 1 A foy (1 G (u + z))du}.

Finally, by Theorem 2, and an explicit calculation using this last expression for H, the proof of Theorem 1 can be completed after a brief calculation. The proof of Corollary 1 is similarly completed when we use this for H in Corollary 2, and then simplify.

4. Connections including queuting theory

Our Theorem 2 generalizes a result of TakAcs [ 151 on particle counters and builds on his elegant idea of obtaining two expressions for the Laplace transform of the renewal measure of a counting process (see.also [2]). The novelty here rests in three places: (1) seeing that the counting method comfortably generalizes to the modified coverage

Transient behavior of coverage processes 599

process, (2) noting that the modified clump provides a tool for obtaining the clump length distribution for the exceptional coverage process, and (3) identifying the distributional identity that permits the calculation of the distribution of the depletion time D (y) as a special clump length distribution.

The clump length in an ordinary coverage process is equivalent to the busy period in an ordinary M/G/oo queueing system, where the line segment lengths are viewed as service times (see [71, [13], [21). The distribution of T(y) was obtained previously for this system (see [ 11, [ 111) and is commonly referred to as the occupation time, socalled due to the fact that this is equivalent to the amount of time after y the system remains ,occupied' if no future arrivals are allowed into service after time y. The results of our Theorem 1 are new and extend this result considerably, as the depletion time, D(y), is then the amount of time the system remains occupied when all future arrivals are allowed to enter into service.

As observed previously, the modified clump is equivalent to a busy period in an MIG100

queue with exceptionalfirst service, that is, a system in which every customer ' who enters

an idle system hence every busy period initiator has a different service distribution

from those customers who arrive to find the system already busy. Models incorporating

this modification have found wide use in singleserver systems, and are commonly

referred to as 'vacation models' (see the references in [5]), but systems with multiple

servers seem to have been overlooked in this regard. One of the most important

applications of such models is to the study of systems with ancillary service requests of

secondary priority that are still attended to by a common service unit, such as a 'polling

system' (see e.g. [31).

One recent application that makes use of our Theorem 2 is a model of a database system that processes two types of transactions: the read transaction, and the write transaction. The read transactions are processed in parallel, while the writes are processed serially. In [91, a new locking protocol is proposed that ensures that all read requests that arrive during a read transaction proceed directly into service, while all read requests that arrive during a write transaction must queue up until that write transaction is completed (i.e. the reads have nonpreemptive priority over the writes). The read requests are all assumed to be i.i.d. from a c.d.f. G(x), and to arrive according to a homogenous simple Poisson stream with rate A.

Thus there are essentially two types of readsessions that take place in the system, those that are initiated by a read request that arrived to find no ongoing transactions, and those that are initiated by read requests that arrived during a write transaction. A read request that encounters no ongoing transactions upon its arrival initiates a read session whose distribution is equivalent to an ordinary busy period of an MIG100 system, while a read session initiated by requests that arrived during a write session is clearly equivalent to a busy period in an M/G/oo queue that is initiated by K customers, where K is the random number of read requests that arrived during the write transaction.

If we let w be the (fixed) time it takes for a write transaction to be concluded, and suppose that at least one read request arrived during the write transaction, and let B,, denote the duration of the ensuing read session, then as a direct consequence of Theorem 2 and its corollary, we have the following result.

600 SID BROWNE AND J. MICHAEL STEELE

Corollary 3. E(exp( sBJ) = 1 0(s)lu(s) wherep(s) has been previously defined, and

(13) 0(s) = A 1 exp( Aw(l G(x))) exp sx A (1 G(u))du dx,

£ 1 exp( Aw) £

and

(14) E(Bw) 1 exp( Aw(l G(x))) exl) A (1 G(u))du dx.

E 1 exp( Aw) (

This can be proved by first realizing that B, is equivalent in distribution to the modified clump l~, considered earlier, where the distribution of the first line segment is equal to the maximum of all the service requests of all the queued read customers that enter simultaneously into service at the end of a write transaction. (This can be established by the same argument as in the proof of Lemma 4.) As such, Theorem 2 applies directly with

H(x) = P(max{SI, S2,. SK) < x),

where S, G and K k_ 1 denotes the number of (truncated) Poisson arrivals during a time w, i.e. P(K = k) = (exp(Aw) 1) 1((AW)klk!), for k ~!: 1. Elementary calculations then show that

exp(AwG(x)) 1

H(x) = exp(Aw) 1

and one may now substitute this form for H into our previous results to complete the proof.

Acknowledgement

The research for this paper was supported in part by a Columbia Business School faculty research grant and by NSF grant DMS9211634 and ARO grant DAAL0391GO 110.

References

[11 BROWN, M. AND Ross, S. M. (1969) Some results for infinite server Poisson queues. J. Appl. Prob. 6, 604611.

[21 BROWN, M. AND SOLOMON, H. (1974) Some results for secondary processes generated by a Poisson process. Stoch. Proc. Appl. 2, 337348.

[3] BROWNE, S. AND YECHIALI, U. (1989) Dynamic priority rules for cyclic type queues. Adv. Appl. Prob. 21, 432450.

[41 COWAN, R. D. (1989) Objects arranged randomly in space: an accessible theory. Adv. Appl. Prob. 21,543569.

[51 Dosm, B. (1986) Queucing systems with vacations a survey. QUESTA 1, 2966.

[6] GLYNN, P. W. AND WRITT, W. (1988) Ordinary CLT and WLLN versions of L A W. Math. Operat. Res. 13, 674692.

[71 HALL, P. (1988) Introduction to the Theory of Coverage Processes. Wiley, New York.

Transient behavior of coverage processes 601

[81 KEILSON, J. AND RAMASWAMY, R. (1988) The backlog and depletiontime process for MIG1 1 vacation models with exhaustive service. J. Appl. Prob. 25, 404412.

[91 KULKARNI, V. G. AND PURYEAR, L. C. (1992) A queueing model for data base systems. University of North Carolina at Chapel Hill, Technical Report No. UNC/ORITR/923, Feb. 1992.

( 101 RAMALHOTO, M. F. (1984) Bounds for the variance of the busy period of the MIGIcr, queue. Adv. Appl. Prob. 16, 929932.

[ 111 SHANBAG, D. N. (1966) On infinite server queues with batch arrivals. J. Appl. Prob. 3, 274279.

[121 STADJE, W. (1985) The busy period of the queueing system MIG100. J. Appl. Prob. 22, 697704.

[13] STADJE, W. (1989) Coverage problems for random intervals. SIAM J. Appl. Math. 49, 15381551.

[141 STOYAN, D., KENDALL, W. S. AND MECKE, J. (1987) Stochastic Geometry and its Applications. Wiley, New York.

[ 151 TAKACS, L. (19 5 6) On a probability problem arising in the theory of counters. Proc.. Camb. Phil. Soc. 52, 488498.

[l 61 TAKACS, L. (1962) Introduction to the Theory of Queues. Oxford University Press, New York.

[ 171 WIDDER, D. V. (194 1) The Laplace Transform. Princeton University Press.

i

i

i

i

i

i