1,721,043 research outputs found
Steady-state GI/G/n queue in the Halfin–Whitt regime
No full textWe consider the FCFS GI/G/n queue in the so-called Halfin–Whitt heavy traffic regime. We prove that under minor technical conditions the associated sequence of steady-state queue length distributions, normalized by n[superscript 1/2], is tight. We derive an upper bound on the large deviation exponent of the limiting steady-state queue length matching that conjectured by Gamarnik and Momcilovic [Adv. in Appl. Probab. 40 (2008) 548–577]. We also prove a matching lower bound when the arrival process is Poisson.
Our main proof technique is the derivation of new and simple bounds for the FCFS GI/G/n queue. Our bounds are of a structural nature, hold for all n and all times t ≥ 0, and have intuitive closed-form representations as the suprema of certain natural processes which converge weakly to Gaussian processes. We further illustrate the utility of this methodology by deriving the first nontrivial bounds for the weak limit process studied in [Ann. Appl. Probab. 19 (2009) 2211–2269].National Science Foundation (U.S.) (Grant CMMI-0726733
On deciding stability of multiclass queueing networks under buffer priority scheduling policies
No full textOne of the basic properties of a queueing network is stability. Roughly speaking, it is the property that the total number of jobs in the network remains bounded as a function of time. One of the key questions related to the stability issue is how to determine the exact conditions under which a given queueing network operating under a given scheduling policy remains stable. While there was much initial progress in addressing this question, most of the results obtained were partial at best and so the complete characterization of stable queueing networks is still lacking.
In this paper, we resolve this open problem, albeit in a somewhat unexpected way. We show that characterizing stable queueing networks is an algorithmically undecidable problem for the case of nonpreemptive static buffer priority scheduling policies and deterministic interarrival and service times. Thus, no constructive characterization of stable queueing networks operating under this class of policies is possible. The result is established for queueing networks with finite and infinite buffer sizes and possibly zero service times, although we conjecture that it also holds in the case of models with only infinite buffers and nonzero service times. Our approach extends an earlier related work [Math. Oper. Res. 27 (2002) 272–293] and uses the so-called counter machine device as a reduction tool.National Science Foundation (U.S.) (Grant CMMI-0726733
On the rate of convergence to stationarity of the M/M/N queue in the Halfin–Whitt regime
No full textWe prove several results about the rate of convergence to stationarity, that is, the spectral gap, for the M/M/n queue in the Halfin–Whitt regime. We identify the limiting rate of convergence to steady-state, and discover an asymptotic phase transition that occurs w.r.t. this rate. In particular, we demonstrate the existence of a constant B[superscript ∗] ≈ 1.85772 s.t. when a certain excess parameter B ∈ (0,B[superscript ∗]], the error in the steady-state approximation converges exponentially fast to zero at rate B[superscript 2 over 4]. For B > B[superscript ∗], the error in the steady-state approximation converges exponentially fast to zero at a different rate, which is the solution to an explicit equation given in terms of special functions. This result may be interpreted as an asymptotic version of a phase transition proven to occur for any fixed n by van Doorn [Stochastic Monotonicity and Queueing Applications of Birth-death Processes (1981) Springer].
We also prove explicit bounds on the distance to stationarity for the M/M/n queue in the Halfin–Whitt regime, when B < B[superscript ∗]. Our bounds scale independently of n in the Halfin–Whitt regime, and do not follow from the weak-convergence theory.National Science Foundation (U.S.) (Grant CMMI-0726733
On Exponential Ergodicity of Multiclass Queueing Networks
No full textOne of the key performance measures in queueing systems is the exponential
decay rate of the steady-state tail probabilities of the queue lengths. It is known
that if a corresponding fluid model is stable and the stochastic primitives have
finite moments, then the queue lengths also have finite moments, so that the tail
probability P(· > s) decays faster than s−n [s superscript -n] for any n. It is natural to conjecture
that the decay rate is in fact exponential.
In this paper an example is constructed to demonstrate that this conjecture
is false. For a specific stationary policy applied to a network with exponentially
distributed interarrival and service times it is shown that the corresponding fluid
limit model is stable, but the tail probability for the buffer length decays slower
than s−log s [s superscript -log s]
Giant Component in Random Multipartite Graphs with given Degree Sequences
Get PDFWe study the problem of the existence of a giant component in a random multipartite graph. We consider a random multipartite graph with p parts generated according to a given degree sequence n[superscript d][subscript i](n),n≥1 which denotes the number of vertices in part i of the multipartite graph with degree given by the vector d in an n-node graph. We assume that the empirical distribution of the degree sequence converges to a limiting probability distribution. Under certain mild regularity assumptions, we characterize the conditions under which, with high probability, there exists a component of linear size. The characterization involves checking whether the Perron-Frobenius norm of the matrix of means of a certain associated edge-biased distribution is greater than unity. We also specify the size of the giant component when it exists. We use the exploration process of Molloy and Reed Molloy and Reed (1995) to analyze the size of components in the random graph. The main challenges arise due to the multidimensionality of the random processes involved which prevents us from directly applying the techniques from the standard unipartite case. In this paper we use techniques from the theory of multidimensional Galton-Watson processes along with Lyapunov function technique to overcome the challenges
The stability of the deterministic Skorokhod problem is undecidable
No full textThe Skorokhod problem arises in studying reflected Brownian motion (RBM) and the associated fluid model on the non-negative orthant. This problem specifically arises in the context of queueing networks in the heavy traffic regime. One of the key problems is that of determining, for a given deterministic Skorokhod problem, whether for every initial condition all solutions of the problem staring from the initial condition are attracted to the origin. The conditions for this attraction property, called stability, are known in dimension up to three, but not for general dimensions. In this paper we explain the fundamental difficulties encountered in trying to establish stability conditions for general dimensions. We prove the existence of dimension d[subscript 0] such that stability of the Skorokhod problem associated with a fluid model of an RBM in dimension d ≥ d[subscript 0] is an undecidable property, when the starting state is a part of the input. Namely, there does not exist an algorithm (a constructive procedure) for identifying stable Skorokhod problem in dimensions d ≥ d[subscript 0].National Science Foundation (U.S.) (Grant CMMI-0726733
A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
Get PDFWe consider the problem of computing the permanent of a n by n matrix. For a class of matrices corresponding to constant degree expanders we construct a deterministic polynomial time approximation algorithm to within a multiplicative factor ( 1 + ∈)[superscript η] for arbitrary∈ > 0. This is an improvement over the best known approximation factor e[superscript η] obtained in Linial, Samorodnitsky and Wigderson (2000), though the latter result was established for arbitrary non-negative matrices. Our results use a recently developed deterministic approximation algorithm for counting partial matchings of a graph (Bayati, Gamarnik, Katz, Nair and Tetali (2007)) and Jerrum–Vazirani method (Jerrum and Vazirani (1996)) of approximating permanent by near perfect matchings
Right-convergence of sparse random graphs
Get PDFThe paper is devoted to the problem of establishing right-convergence of sparse random graphs. This concerns the convergence of the logarithm of number of homomorphisms from graphs or hyper-graphs GN,N≥1 to some target graph W . The theory of dense graph convergence, including random dense graphs, is now well understood (Borgs et al. in Ann Math 176:151–219, 2012; Borgs et al. in Adv Math 219:1801–1851, 2008; Chatterjee and Varadhan in Eur J Comb 32:1000–1017, 2011; Lovász and Szegedy in J Comb Theory Ser B 96:933–957, 2006), but its counterpart for sparse random graphs presents some fundamental difficulties. Phrased in the statistical physics terminology, the issue is the existence of the limits of appropriately normalized log-partition functions, also known as free energy limits, for the Gibbs distribution associated with W . In this paper we prove that the sequence of sparse Erdös-Rényi graphs is right-converging when the tensor product associated with the target graph W satisfies a certain convexity property. We treat the case of discrete and continuous target graphs W . The latter case allows us to prove a special case of Talagrand’s recent conjecture [more accurately stated as level III Research Problem 6.7.2 in his recent book (Talagrand in Mean Field Models for Spin Glasses: Volume I: Basic examples. Springer, Berlin, 2010)], concerning the existence of the limit of the measure of a set obtained from RN by intersecting it with linearly in N many subsets, generated according to some common probability law. Our proof is based on the interpolation technique, introduced first by Guerra and Toninelli (Commun Math Phys 230:71–79, 2002) and developed further in (Abbe and Montanari in On the concentration of the number of solutions of random satisfiability formulas, 2013; Bayati et al. in Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010; Contucci et al. in Antiferromagnetic Potts model on the Erdös-Rényi random graph, 2011; Franz and Leone in J Stat Phys 111(3/4):535–564, 2003; Franz et al. in J Phys A Math Gen 36:10967–10985, 2003; Montanari in IEEE Trans Inf Theory 51(9):3221–3246, 2005; Panchenko and Talagrand in Probab Theory Relat Fields 130:312–336, 2004). Specifically, Bayati et al. (Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010) establishes the right-convergence property for Erdös-Rényi graphs for some special cases of W . In this paper most of the results in Bayati et al. (Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010) follow as a special case of our main theorem.National Science Foundation (U.S.) (NSF grant CMMI-1031332
Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution
Get PDFWe consider a heterogeneous queueing system consisting of one large pool of O(r) identical servers, where r→∞ is the scaling parameter. The arriving customers belong to one of several classes which determines the service times in the distributional sense. The system is heavily loaded in the Halfin–Whitt sense, namely the nominal utilization is 1−a/r√ where a>0 is the spare capacity parameter. Our goal is to obtain bounds on the steady state performance metrics such as the number of customers waiting in the queue Q [superscript r] (∞). While there is a rich literature on deriving process level (transient) scaling limits for such systems, the results for steady state are primarily limited to the single class case.
This paper is the first one to address the case of heterogeneity in the steady state regime. Moreover, our results hold for any service policy which does not admit server idling when there are customers waiting in the queue. We assume that the interarrival and service times have exponential distribution, and that customers of each class may abandon while waiting in the queue at a certain rate (which may be zero). We obtain upper bounds of the form O(r√) on both Q [superscript r] (∞) and the number of idle servers. The bounds are uniform w.r.t. parameter r and the service policy. In particular, we show that lim sup[subscript r]Eexp(θr[superscript −1/2)Q[superscript r](∞))0.National Science Foundation (U.S.) (Grant CMMI-0726733
A Note on Alternating Minimization Algorithm for the Matrix Completion Problem
Get PDFWe consider the problem of reconstructing a low-rank matrix from a subset of its entries and analyze two variants of the so-called alternating minimization algorithm, which has been proposed in the past. We establish that when the underlying matrix has rank one, has positive bounded entries, and the graph underlying the revealed entries has diameter which is logarithmic in the size of the matrix, both algorithms succeed in reconstructing the matrix approximately in polynomial time starting from an arbitrary initialization. We further provide simulation results which suggest that the second variant which is based on the message passing type updates performs significantly better
- …
