Waiting-Time Distributions in Polling Systems with Simultaneous Batch Arrivals

We study the delay in asymmetric cyclic polling models with general mixtures of gated and exhaustive service, with generally distributed service times and switch-over times, and in which batches of customers may arrive simultaneously at the different queues. We show that (1–)X _i converges to a gamma distribution with known parameters as the offered load tends to unity, where X _i is the steady-state length of queue i at an arbitrary polling instant at that queue. The result is shown to lead to closed-form expressions for the Laplace–Stieltjes transform (LST) of the waiting-time distributions at each of the queues (under proper scalings), in a general parameter setting. The results show explicitly how the distribution of the delay depends on the system parameters, and in particular, on the simultaneity of the arrivals. The results also suggest simple and fast approximations for the tail probabilities and the moments of the delay in stable polling systems, explicitly capturing the impact of the correlation structure in the arrival processes. Numerical experiments indicate that the approximations are accurate for medium and heavily loaded systems.     

Stochastic bounds for a polling system

In this note we consider two queueing systems: a symmetric polling system with gated service at allN queues and with switchover times, and a single-server single-queue model with one arrival stream of ordinary customers andN additional permanently present customers. It is assumed that the combined arrival process at the queues of the polling system coincides with the arrival process of the ordinary customers in the single-queue model, and that the service time and switchover time distributions of the polling model coincide with the service time distributions of the ordinary and permanent customers, respectively, in the single-queue model. A complete equivalence between both models is accomplished by the following queue insertion of arriving customers. In the single-queue model, an arriving ordinary customer occupies with probabilityp _i a position at the end of the queue section behind theith permanent customer,i = l, ...,N. In the cyclic polling model, an arriving customer with probabilityp _i joins the end of theith queue to be visited by the server, measured from its present position.For the single-queue model we prove that, if two queue insertion distributions {p _{i, i} = l, ...,N} and {q _{i, i} = l, ...,N} are stochastically ordered, then also the workload and queue length distributions in the corresponding two single-queue versions are stochastically ordered. This immediately leads to equivalent stochastic orderings in polling models.Finally, the single-queue model with Poisson arrivals andp ₁ = 1 is studied in detail.Part of the research of the first author has been supported by the Esprit BRA project QMIPS.     

A Load-Balanced Network with Two Servers

A load-balanced network with two queues Q ₁ and Q ₂ is considered. Each queue receives a Poisson stream of customers at rate _i , i=1,2. In addition, a Poisson stream of rate arrives to the system; the customers from this stream join the shorter of two queues. After being served in the ith queue, i=1,2, customers leave the system with probability 1–p _i ^*, join the jth queue with probability p(i,j), j=1,2, and choose the shortest of two queues with probability p(i,{1,2}). We establish necessary and sufficient conditions for stability of the system.     

A queueing network with a single cyclically roving server

A queueingnetwork that is served by asingle server in a cyclic order is analyzed in this paper. Customers arrive at the queues from outside the network according to independent Poisson processes. Upon completion of his service, a customer mayleave the network, berouted to another queue in the network orrejoin the same queue for another portion of service. The single server moves through the different queues of the network in a cyclic manner. Whenever the server arrives at a queue (polls the queue), he serves the waiting customers in that queue according to some service discipline. Both the gated and the exhaustive disciplines are considered. When moving from one queue to the next queue, the server incurs a switch-over period. This queueing network model has many applications in communication, computer, robotics and manufacturing systems. Examples include token rings, single-processor multi-task systems and others. For this model, we derive the generating function and the expected number of customers present in the network queues at arbitrary epochs, and compute the expected values of the delays observed by the customers. In addition, we derive the expected delay of customers that follow a specific route in the network, and we introduce pseudo-conservation laws for this network of queues.Summary of notation B_i, B _i ^* (s) service time of a customer at queue i and its LST - b_i, b_i ⁽²⁾ mean and second moment of B_i - R_i, R _i ^* (s) duration of switch-over period from queue i and its LST - r_i, r_i mean and second moment of R_i - r, r⁽²⁾ mean and second moment of _i ^N =₁R_i - _i external arrival rate of type-i customers - _i total arrival rate into queue i - _i utilization of queue i; _i=_i - system utilization _i ^N =_1i - c=E[C] the expected cycle length - X _i ^j number of customers in queue j when queue i is polled - X_i=X _i ⁱ number of customers residing in queue i when it is polled - f_i(j) - X _i ^* number of customers residing in queue i at an arbitrary moment - Y_i the duration of a service period of queue i - W_i,T_i the waiting time and sojourn time of an arbitary customer at queue i - F^*(z₁, z₂,..., z_N) GF of number of customers present at the queues at arbitrary moments - F_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at polling instants of queue i - ¯F_i(z₁, z₂,...,z_N) GF of number of customers present at the queues at switching instants of queue i - V_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at service initiation instants at queue i - ¯V_i(z₁,z₂,...,z_N) GF of number of customers present at the queues at service completion instants at queue i The work of this author was supported by the Bernstein Fund for the Promotion of Research and by the Fund for the Promotion of Research at the Technion.Part of this work was done while H. Levy was with AT&T Bell Laboratories.     

Uniformly More Powerful, Two-Sided Tests for Hypotheses about Linear Inequalities

Let Xhave a multivariate, p-dimensional normal distribution (p 2) with unknown mean and known, nonsingular covariance . Consider testing H ₀ : b _i 0, for some i = 1,..., k, and b _i 0, for some i = 1,..., k, versus H ₁ : b _i < 0, for all i = 1,..., k, or b _i < 0, for all i = 1,..., k, where b ₁,..., b _k , k 2, are known vectors that define the hypotheses and suppose that for each i = 1,..., k there is an j {1,..., k} (j will depend on i) such that b _i b _j 0. For any 0 < < 1/2. We construct a test that has the same size as the likelihood ratio test (LRT) and is uniformly more powerful than the LRT. The proposed test is an intersection-union test. We apply the result to compare linear regression functions.     

Geometric Hermite interpolation by spatial Pythagorean-hodograph cubics

It is shown that, depending upon the orientation of the end tangents t₀,t₁ relative to the end point displacement vector p=p₁–p₀, the problem of G¹ Hermite interpolation by PH cubic segments may admit zero, one, or two distinct solutions. For cases where two interpolants exist, the bending energy may be used to select among them. In cases where no solution exists, we determine the minimal adjustment of one end tangent that permits a spatial PH cubic Hermite interpolant. The problem of assigning tangents to a sequence of points p₀,...,p_n in R³, compatible with a G¹ piecewise-PH-cubic spline interpolating those points, is also briefly addressed. The performance of these methods, in terms of overall smoothness and shape-preservation properties of the resulting curves, is illustrated by a selection of computed examples.     

More on P-Stable Convex Sets in Banach Spaces

We study the asymptotic behavior and limit distributions for sums S _n =b_n ^-1 _i=1 ⁿ _i,where _i, i 1, are i.i.d. random convex compact (cc) sets in a given separable Banach space B and summation is defined in a sense of Minkowski. The following results are obtained: (i) Series (LePage type) and Poisson integral representations of random stable cc sets in B are established; (ii) The invariance principle for processes S _n(t) =b_n ^-1 _i=1 ^[nt] _i, t[0, 1], and the existence of p-stable cc Levy motion are proved; (iii) In the case, where _i are segments, the limit of S _n is proved to be countable zonotope. Furthermore, if B = R ^d , the singularity of distributions of two countable zonotopes Y_{p 1}, ₁,Y_{p 2}, ₂, corresponding to values of exponents p ₁, p ₂ and spectral measures ₁, ₂, is proved if either p ₁ p ₂ or _{1 2}; (iv) Some new simple estimates of parameters of stable laws in R ^d , based on these results are suggested.     

Departures from queues with changeover times

We consider the M/M ^ij /1 queue as a model of queues with changeover times, i.e., the service is exponential with parameter _ij depending on the previous job type (i) and the current job type (j). It is shown that the departure process is renewal and Poisson iff _ij = (constant). In this case, types of departures are dependent renewal processes. Crosscovariance and crosscorrelations are given.     

Exact Asymptotics for k i -limited Exponential Polling Models

In this paper we find exact asymptotic expressions for the event that the total queue length is large for a k _i -limited exponential polling model with equal service rates and two classes of customer. It is found that this behaviour divides into two very different regimes, depending on the arrival rates to the system. Using these exact asymptotic expressions, we provide heuristics for choosing the k _i values to provide a given level of quality of service to one class while giving best effort to the other class.     

Ruin Probabilities under a Markovian Risk Model

In this paper, a Markovian risk model is developed, in which the occurrence of the claims is described by a point process {N(t)}t≥0 with N(t) being the number of jumps of a Markov chain during the interval [0, t]. For the model, the explicit form of the ruin probability ψ(0) and the bound for the convergence rate of the ruin probability ψ(u) are given by using the generalized renewal technique developed in this paper.Finally, we prove that the ruin probability ψ(u) is a linear combination of some negative exponential functions in a special case when the claims are exponentially distributed and the Markov chain has an intensity matrix(qij)i,j∈E such that qm = qml and qi=qi(i 1), 1≤i≤m-1.     

Trigonometric Widths of the Classes L β,p Ψ of Functions of Many Variables

We obtain order estimates for the trigonometric widths of the classes L _,p of periodic functions of many variables in the space L _q for 1 < p 2 q < p/(p – 1).     

Laguerre Polynomials, Restriction Principle, and Holomorphic Representations of SL(2,R)

The restriction principle is used to implement a realization of the holomorphic representations of SL(2,R) on L ² (R ⁺,t dt) by way of the standard upper half plane realization. The resulting unitary equivalence establishes a correspondence between functions that transform according to the character e^–i(2n++1); under rotations and the Laguerre polynomials. The standard recursion relations amongst Laguerre polynomials are derived from the action of the Lie algebra.     

Stability of the C *-Algebra Associated with Twisted CCR

The universal enveloping C ^*-algebra A of twisted canonical commutation relations is considered. It is shown that, for any (–1,1), the C ^*-algebra A is isomorphic to the C ^*-algebra A ₀ generated by partial isometries t _i ,t _i ^*,i=1,¨,d satisfying the relations t _i ^* t _j = _ij (1– _k<i t _k t _k ^*), t _j t _i =0, ij and it is proved that the Fock representation of A is faithful.     

Certain Convolution Operators for Meromorphic Functions

Let (p N) be the class of functions analytic in 0 < |z| < 1. A convolution operator L_p(a, c) on p is introduced. This paper gives some sharp inequalities for f(z) satisfying Re{(1 – )z^pL_p(a, c) f(z) + z^pL_p(a + 1, c) f(z)} > , where 0, < 1, a > 0 and c 0, –1, –2,....AMS Subject Classification (1991) 30C45 30A10     

Function Spaces of Posets with Projections

This paper investigates function spaces of structures consisting of a partially ordered set together with some directed family of projections.More precisely, given a fixed directed index set (I,), we consider triples (D,,(p _i ) _iI ) with (D,) a poset and (p _i ) _iI a monotone net of projections of D. We call them (I,)-pop's (posets with projections). Our main purpose is to study structure preserving maps between (I,)-pop's. Such homomorphisms respect both order and projections.Any (I,)-pop is known to induce a uniformity and thus a topology. The set of all homomorphisms between two (I,)-pop's turns out to form an (I,)-pop itself. We show that its uniformity is the uniformity of uniform convergence. This enables us to prove that properties such as completeness and compactness transfer to function pop's.Concerning categorical properties of (I,)-pop's, we will see that we are in a lucky situation from a computer scientist's point of view: we obtain Cartesian closed categories. Moreover, by a D -construction we get (I,)-pop's that are isomorphic to their own exponent. This yields new models for the untyped -calculus.     

On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

Asymptotic behavior of general M-estimates for regression and scale with random carriers

Summary Let (xini, y _i be a sequence of independent identically distributed random variables, where x _i R ^p and y _i R, and let R ^p be an unknown vector such that y _i =x _i +u _i (^*), where u _i is independent of x _i and has distribution function F(u/), where >0 is an unknown parameter. This paper deals with a general class of M-estimates of regression and scale, ( ^*,^*), defined as solutions of the system: , where r= (y _i –x _i ^1*/)^*, with R ^p ×RR and RR. This class contains estimators of (, ) proposed by Huber, Mallows and Krasker and Welsch. The consistency and asymptotic normality of the general M-estimators are proved assuming general regularity conditions on and and assuming the joint distribution of (x _i , y _i ) to fulfill the model (^*) only approximately.     

Minimization of the maximal penalty in the case of preemption of jobs

For a class of structural sets of penalty functions={_i} _i=1 ⁿ with lower quasiconvex functions _i defined for sets of jobs={_i} _i=1 ⁿ , one gives an algorithm for solving the problem n /1/ preemp ¦ max, having order 0(np), where n is the number of jobs _i and p is the total length of the completion of all jobs of the set.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 102, pp. 61–67, 1980.In conclusion, the author expresses her gratitude to K. V. Shakhbazyan for his interest in this paper.     

Weakly Associated Prime Filtration

Let R be a (not necessarily Noetherian) commutative ring and let M be a (not necessarily finitely generated) R-module. We characterize the modules with only finitely many weakly associated primes as those modules M admitting a chain 0 = M ₀ M ₁ ... M _n = M of submodules together with prime ideals p₁, p₂,...,p _n such that the set of weakly associated primes of M _i /M _i-1 is equal to {p _i } for all 1 i n. Let M = gr_a(M) = _n0a ⁿ M/a ⁿ⁺¹ M be the corresponding graded module over the graded ring R = gr_a(R) = _n0a ⁿ /a ⁿ⁺¹. It is shown that the union of the set of weakly associated primes of.....