Queueing Systems
Journal Prestige (SJR): 0.809 Citation Impact (citeScore): 1 Number of Followers: 7 Hybrid journal (It can contain Open Access articles) ISSN (Print) 15729443  ISSN (Online) 02570130 Published by SpringerVerlag [2469 journals] 
 Large deviations for stochastic fluid networks with Weibullian tails

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We consider a stochastic fluid network where the external input processes are compound Poisson with heavytailed Weibullian jumps. Our results comprise of large deviations estimates for the buffer content process in the vectorvalued Skorokhod space which is endowed with the product \(J_1\) topology. To illustrate our framework, we provide explicit results for a tandem queue. At the heart of our proof is a recent samplepath large deviations result, and a novel continuity result for the Skorokhod reflection map in the product \(J_1\) topology.
PubDate: 20220927

 State space collapse for multiclass queueing networks under SBP service
policies
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In Braverman et al. [3], the authors justify the steadystate diffusion approximation of a multiclass queueing network under static buffer priority policy in heavy traffic. A major assumption in [3] is the moment state space collapse (momentSSC) property of the steadystate queue length. In this paper, we prove that momentSSC holds under a corresponding state space collapse condition on the fluid model. Our approach is inspired by Dai and Meyn [8], which was later adopted by Budhiraja and Lee [4] to justify the diffusion approximation for generalized Jackson networks. We will verify that the fluid state space collapse holds for various networks.
PubDate: 20220913

 Functional equations with multiple recursive terms

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In this paper, we study a functional equation for generating functions of the form \(f(z) = g(z) \sum _{i=1}^M p_i f(\alpha _i(z)) + K(z)\) , viz. a recursion with multiple recursive terms. We derive and analyze the solution of this equation for the case that the \(\alpha _i(z)\) are commutative contraction mappings. The results are applied to a wide range of queueing, autoregressive and branching processes.
PubDate: 20220904

 Fork–join and redundancy systems with heavytailed job sizes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We investigate the tail asymptotics of the response time distribution for the cancelonstart (c.o.s.) and canceloncompletion (c.o.c.) variants of redundancyd scheduling and the fork–join model with heavytailed job sizes. We present bounds, which only differ in the prefactor, for the tail probability of the response time in the case of the firstcome firstserved discipline. For the c.o.s. variant, we restrict ourselves to redundancyd scheduling, which is a special case of the fork–join model. In particular, for regularly varying job sizes with tail index \(\nu \) the tail index of the response time for the c.o.s. variant of redundancyd equals  \(\min \{d_{\mathrm {cap}}(\nu 1),\nu \}\) , where \(d_{\mathrm {cap}} = \min \{d,Nk\}\) , N is the number of servers and k is the integer part of the load. This result indicates that for \(d_{\mathrm {cap}} < \frac{\nu }{\nu 1}\) the waiting time component is dominant, whereas for \(d_{\mathrm {cap}} > \frac{\nu }{\nu 1}\) the job size component is dominant. Thus, having \(d = \lceil \min \{\frac{\nu }{\nu 1},Nk\} \rceil \) replicas is sufficient to achieve the optimal asymptotic tail behavior of the response time. For the c.o.c. variant of the fork–join ( \(n_{\mathrm {F}},n_{\mathrm {J}}\) ) model, the tail index of the response time, under some assumptions on the load, equals \(1\nu \) and \(1(n_{\mathrm {F}}+1n_{\mathrm {J}})\nu \) , for identical and i.i.d. replicas, respectively; here, the waiting time component is always dominant.
PubDate: 20220901

 Tail asymptotics in any direction of the stationary distribution in a
twodimensional discretetime QBD process
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We consider a discretetime twodimensional quasibirthanddeath process (2dQBD process for short) \(\{(\varvec{X}_n,J_n)\}\) on \(\mathbb {Z}_+^2\times S_0\) , where \(\varvec{X}_n=(X_{1,n},X_{2,n})\) is the level state, \(J_n\) the phase state (background state) and \(S_0\) a finite set, and study asymptotic properties of the stationary tail distribution. The 2dQBD process is an extension of usual onedimensional QBD process. By using the matrix analytic method of the queueing theory and the complex analytic method, we obtain the asymptotic decay rate of the stationary tail distribution in an arbitrary direction. This result is an extension of the corresponding result for a certain twodimensional reflecting random work without background processes, obtained by using the large deviation techniques and the singularity analysis methods. We also present a condition ensuring the sequence of the stationary probabilities geometrically decays without power terms, asymptotically. Asymptotic properties of the stationary tail distribution in the coordinate directions in a 2dQBD process have already been studied in the literature. The results of this paper are also important complements to those results.
PubDate: 20220830

 Derivative of the expected supremum of fractional Brownian motion at
$$H=1$$ H = 1
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract The Hderivative of the expected supremum of fractional Brownian motion \(\{B_H(t),t\in {\mathbb {R}}_+\}\) with drift \(a\in {\mathbb {R}}\) over time interval [0, T] $$\begin{aligned} \frac{\partial }{\partial H} {\mathbb {E}}\Big (\sup _{t\in [0,T]} B_H(t)  at\Big ) \end{aligned}$$ at \(H=1\) is found. This formula depends on the quantity \({\mathscr {I}}\) , which has a probabilistic form. The numerical value of \({\mathscr {I}}\) is unknown; however, Monte Carlo experiments suggest \({\mathscr {I}}\approx 0.95\) . As a byproduct we establish a weak limit theorem in C[0, 1] for the fractional Brownian bridge, as \(H\uparrow 1\) .
PubDate: 20220830

 Subexponential asymptotics of asymptotically blockToeplitz and upper
blockHessenberg Markov chains
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract This paper studies the subexponential asymptotics of the stationary distribution vector of an asymptotically blockToeplitz and upper blockHessenberg (atUBH) Markov chain in discrete time. The atUBH Markov chain is a kind of the upper blockHessenberg (UBH) one and is a generalization of the M/G/1type one. The atUBH Markov chain typically arises from semiMarkovian retrial queues, as the queuelength process, its embedded process, or appropriately timescaled versions of these processes. In this paper, we present subexponential and locally subexponential asymptotic formulas for the stationary distribution vector. We then extend the locally subexponential asymptotic formula to a continuoustime version of the atUBH Markov chain by uniformization and change of time scale. This extension expands the applicability of the locally subexponential asymptotic formula.
PubDate: 20220830

 Queueing and risk models with dependencies

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract This paper analyzes various stochastic recursions that arise in queueing and insurance risk models with a ‘semilinear’ dependence structure. For example, an interarrival time depends on the workload, or the capital, immediately after the previous arrival; or the service time of a customer depends on her waiting time. In each case, we derive and solve a fixedpoint equation for the Laplace–Stieltjes transform of a key performance measure of the model, like waiting time or ruin time.
PubDate: 20220829

 Editorial introduction to the special issue “Masakiyo
Miyazawa—75”
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
PubDate: 20220829

 Optimal staffing for ticket queues

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Ticket queues are popular in many service systems. Upon arrival, each customer is issued a numbered ticket and receives service on a firstcomefirstserved basis according to the ticket number. There is no physical queue; customers may choose to walk away and return later (before their numbers are called) to receive service. We study the problem of optimal staffing in such a system with two capacity levels, where the staffing decision can only be based on ticket numbers, as opposed to the physical queue length in a traditional system. Using renewal reward theorem, we first derive the longrun average total cost (including customer delay and abandonment costs, operating cost and cost for changing staffing levels) and then obtain the optimal solution using fractional programming. In addition, we pursue a randomwalk analysis, which leads to some highly accurate approximations.
PubDate: 20220826

 On busy periods of the critical GI/G/1 queue and BRAVO

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study critical GI/G/1 queues under finite secondmoment assumptions. We show that the busyperiod distribution is regularly varying with index half. We also review previously known M/G/1/ and M/M/1 derivations, yielding exact asymptotics as well as a similar derivation for GI/M/1. The busyperiod asymptotics determine the growth rate of moments of the renewal process counting busy cycles. We further use this to demonstrate a Balancing Reduces Asymptotic Variance of Outputs (BRAVO) phenomenon for the workoutput process (namely the busy time). This yields new insight on the BRAVO effect. A second contribution of the paper is in settling previous conjectured results about GI/G/1 and GI/G/s BRAVO. Previously, infinite buffer BRAVO was generally only settled under fourthmoment assumptions together with an assumption about the tail of the busy period. In the current paper, we strengthen the previous results by reducing to assumptions to existence of \(2+\epsilon \) moments.
PubDate: 20220822

 Age of information using Markovrenewal methods

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract When designing a message transmission system, from the point of view of making sure that the information transmitted is as fresh as possible, two rules of thumb seem reasonable: use small buffers and adopt a lastinfirstout policy. In this paper, the freshness of information is interpreted as the recently studied “age of information” performance measure. Considering it as a stochastic process operating in a stationary regime, we compute the whole marginal distribution of the age of information for some wellperforming systems. We assume that the arrival process is Poisson and that the messages have independent service times with common distribution, i.e., the M/GI model. We demonstrate the usefulness of Palm and Markovrenewal theory to derive results for Laplace transforms. Our numerical studies address some aspects of open questions regarding the optimality of previously proposed scheduling policies, and a policy newly considered herein, for AoI management.
PubDate: 20220817

 A dual skew symmetry for transient reflected Brownian motion in an orthant

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We introduce a transient reflected Brownian motion in a multidimensional orthant, which is either absorbed at the apex of the cone or escapes to infinity. We address the question of computing the absorption probability, as a function of the starting point of the process. We provide a necessary and sufficient condition for the absorption probability to admit an exponential product form, namely that the determinant of the reflection matrix is zero. We call this condition a dual skew symmetry. It recalls the famous skew symmetry introduced by Harrison (Adv Appl Probab 10:886–905, 1978), which characterizes the exponential stationary distributions in the recurrent case. The duality comes from that the partial differential equation satisfied by the absorption probability is dual to the one associated with the stationary distribution in the recurrent case.
PubDate: 20220813

 Birth and death processes in interactive random environments

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract This paper studies birth and death processes in interactive random environments where the birth and death rates and the dynamics of the state of the environment are dependent on each other. Two models of a random environment are considered: a continuoustime Markov chain (finite or countably infinite) and a reflected (jump) diffusion process. The background is determined by a joint Markov process carrying a specific interactive mechanism, with an explicit invariant measure whose structure is similar to a product form. We discuss a number of queueing and populationgrowth models and establish conditions under which the abovementioned invariant measure can be derived. Next, an analysis of the rate of convergence to stationarity is performed for the models under consideration. We consider two settings leading to either an exponential or a polynomial convergence rate. In both cases we assume that the underlying environmental Markov process has an exponential rate of convergence, but the convergence rate of the joint Markov process is determined by certain conditions on the birth and death rates. To prove these results, a coupling method turns out to be useful.
PubDate: 20220812

 The periodic steadystate solution for queues with Erlang arrivals and
service and timevarying periodic transition rates
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study a queueing system with Erlang arrivals with k phases and Erlang service with m phases. Transition rates among phases vary periodically with time. For these systems, we derive an analytic solution for the asymptotic periodic distribution of the level and phase as a function of time within the period. The asymptotic periodic distribution is analogous to a steadystate distribution for a system with constant rates. If the time within the period is considered part of the state, then it is a steadystate distribution. We also obtain waiting time and busy period distributions. These solutions are expressed as infinite series. We provide bounds for the error of the estimate obtained by truncating the series. Examples are provided comparing the solution of the system of ordinary differential equation with a truncated state space to these asymptotic solutions involving remarkably few terms of the infinite series. The method can be generalized to other level independent quasibirthdeath processes if the singularities of the generating function are known.
PubDate: 20220810

 A transient symmetry analysis for the M/M/1/k queue

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We develop new techniques involving group symmetries and complex analysis to obtain exact solutions for the transition probabilities of the M/M/1/k queueing process. These methods are based on the underlying Markovian structure of these random processes and do not involve any generating functions, Laplace transforms, or advanced special functions. Our techniques exploit the intrinsic group symmetries for both the state spaces and the matrix generators of the Markov processes related to the M/M/1/k queue. These results complement and extend the previous transient solutions given by Takács (Introduction to the theory of queues. University texts in the mathematical sciences, Oxford University Press, New York, 1962). Much of the inspiration for this work comes from viewing this queueing process as a fundamental Markovian model for the dynamics of a bike sharing station. The exact transient analysis for a related stopped version of this process can be used to address fundamental decisionmaking issues for managing bikesharing services.
PubDate: 20220807

 Analysis of a tripartite entanglement distribution switch

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study a quantum switch that distributes tripartite entangled states to sets of users. The entanglement switching process requires two steps: First, each user attempts to generate bipartite entanglement between itself and the switch, and second, the switch performs local operations and a measurement to create multipartite entanglement for a set of three users. In this work, we study a simple variant of this system, wherein the switch has infinite memory and the links that connect the users to the switch are identical. This problem formulation is of interest to several distributed quantum applications, while the technical aspects of this work result in new contributions within queueing theory. The state of the system is modeled as continuoustime Markov chain (CTMC), and performance metrics of interest (probability of an empty system, switch capacity, expectation, and variance of the number of qubitpairs stored) are computed via the solution of a twodimensional functional equation obtained by reducing it to a boundary value problem on a closed curve. This work is a followup of Nain et al. (Proc ACM Measure Anal Comput Syst(POMACS) 4, 2020) where a switch distributing entangled multipartite states to sets of users was studied, but only the switch capacity and the expected number of stored qubits were derived.
PubDate: 20220801
DOI: 10.1007/s1113402109731w

 Regulation of a singleserver queue with customers who dynamically choose
their service durations
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In recent years, there is a growing attention towards queueing models with customers who choose their service durations. The model assumptions in the existing literature imply that every customer knows his service demand when he enters into the service position. Clearly, this property is not consistent with some reallife situations. Motivated by this issue, the current work includes a singleserver queueing model with customers who dynamically choose their service durations. In this setup, the main result is existence of a quadratic price function which (1) implies an optimal resource allocation from a social point of view and (2) internalizes the externalities in the system. In addition, it is explained how to compute its parameters efficiently.
PubDate: 20220801
DOI: 10.1007/s1113402109722x

 A load balancing system in the manyserver heavytraffic asymptotics

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study a load balancing system in the manyserver heavytraffic regime. We consider a system with N servers, where jobs arrive to the system according to a Poisson process and have an exponentially distributed size with mean 1. We parametrize the arrival rate so that the arrival rate per server is \(1N^{\alpha }\) , where \(\alpha >0\) is a parameter that represents how fast the load grows with respect to the number of servers. The manyserver heavytraffic regime corresponds to the limit as \(N\rightarrow \infty \) , and subsumes several regimes, such as the Halfin–Whitt regime ( \(\alpha =1/2\) ), the NDS regime ( \(\alpha =1\) ), as \(\alpha \downarrow 0\) it approximates mean field and as \(\alpha \rightarrow \infty \) it approximates the classical heavytraffic regime. Most of the prior work focuses on regimes with \(\alpha \in [0,1]\) . In this paper, we focus on the case when \(\alpha >1\) and the routing algorithm is powerofd choices with \(d=\lceil cN^\beta \rceil \) for some constants \(c>0\) and \(\beta \ge 0\) . We prove that \(\alpha +\beta >3\) is sufficient to observe that the average queue length scaled by \(N^{1\alpha }\) converges to an exponential random variable. In other words, if \(\alpha +\beta >3\) , the scaled average queue length behaves similarly to the classical heavytraffic regime. In particular, this result implies that if d is constant, we require \(\alpha >3\) and if routing occurs according to JSQ we require \(\alpha >2\) . We provide two proofs to our result: one based on the Transform method introduced in HurtadoLange and Maguluri (Stoch Syst 10(4):275–309, 2020) and one based on Stein’s method. In the second proof, we also compute the rate of convergence in Wasserstein’s distance. In both cases, we additionally compute the rate of convergence in expected value. All of our proofs are powered by state space collapse.
PubDate: 20220621
DOI: 10.1007/s11134022098477

 Infiniteserver systems with Hawkes arrivals and Hawkes services

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract This paper is devoted to the study of the number of customers in infiniteserver systems driven by Hawkes processes. In these systems, the selfexciting arrival process is assumed to be represented by a Hawkes process and the selfexciting service process by a statedependent Hawkes process (sdHawkes process). Under some suitable conditions, for the \(\mathrm{Hawkes/sdHawkes/\infty }\) system, the Markov property of the system is derived. The joint timedependent distribution of the number of customers in the system, the arrival intensity and the server intensity is characterized by a system of differential equations. Then, the timedependent results are also deduced for the \(\mathrm{M/sdHawkes/\infty }\) system.
PubDate: 20220429
DOI: 10.1007/s11134022098133
