Explore the vast range of titles available.

Under the last-in, first-out (LIFO) discipline, jobs arriving later at a class always receive priority of service over earlier arrivals at any class belonging to the same station. Subcritical LIFO queueing networks with Poisson external arrivals are known to be stable, but an open problem has been whether this is also the case when external arrivals are given by renewal processes. Here, we show that this weaker assumption is not sufficient for stability by constructing a family of examples where the number of jobs in the network increases to infinity over time. This behavior contrasts with that for the other classical disciplines: processor sharing (PS), infinite server (IS) and first-in, first-out (FIFO), which are stable under general conditions on the renewals of external arrivals. Together with LIFO, PS and IS constitute the classical symmetric disciplines; with the inclusion of FIFO, these disciplines constitute the classical homogeneous disciplines. Our examples show that a general theory for stability of either family is doubtful.

Join the shortest queue (JSQ) refers to networks whose incoming jobs are assigned to the shortest queue from among a randomly chosen subset of the queues in the system. After completion of service at the queue, a job leaves the network. We show that, for all nonidling service disciplines and for general interarrival and service time distributions, such networks are stable when they are subcritical. We then obtain uniform bounds on the tails of the marginal distributions of the equilibria for families of such networks; these bounds are employed to show relative compactness of the marginal distributions. We also present a family of subcritical JSQ networks whose workloads in equilibrium are much larger than for the corresponding networks where each incoming job is assigned randomly to a queue. Part of this work generalizes results in [Queueing Syst. 29 (1998) 55–73], which applied fluid limits to study networks with the FIFO discipline. Here, we apply an appropriate Lyapunov function.

Randomized load balancing greatly improves the sharing of resources while being simple to implement. In one such model, jobs arrive according to a rate- αN Poisson process, with α <1, in a system of N rate-1 exponential server queues. In Vvedenskaya et al. (Probl. Inf. Transm. 32:15–29, 1996 ), it was shown that when each arriving job is assigned to the shortest of D , D ≥2, randomly chosen queues, the equilibrium queue sizes decay doubly exponentially in the limit as N →∞. This is a substantial improvement over the case D =1, where queue sizes decay exponentially. The reasoning in Vvedenskaya et al. (Probl. Inf. Transm. 32:15–29, 1996 ) does not easily generalize to jobs with nonexponential service time distributions. A modularized program for treating randomized load balancing problems with general service time distributions was introduced in Bramson et al. (Proc. ACM SIGMETRICS, pp. 275–286, 2010 ). The program relies on an ansatz that asserts that, for a randomized load balancing scheme in equilibrium, any fixed number of queues become independent of one another as N →∞. This allows computation of queue size distributions and other performance measures of interest. In this article, we demonstrate the ansatz in several settings. We consider the least loaded balancing problem, where an arriving job is assigned to the queue with the smallest workload. We also consider the more difficult problem, where an arriving job is assigned to the queue with the fewest jobs, and demonstrate the ansatz when the service discipline is FIFO and the service time distribution has a decreasing hazard rate. Last, we show the ansatz always holds for a sufficiently small arrival rate, as long as the service distribution has 2 moments.

Consider a semimartingale reflecting Brownian motion (SRBM) Z whose state space is the d-dimensional nonnegative orthant. The data for such a process are a drift vector θ, a nonsingular d × d covariance matrix Σ, and a d × d reflection matrix R that specifies the boundary behavior of Z. We say that Z is positive recurrent, or stable, if the expected time to hit an arbitrary open neighborhood of the origin is finite for every starting state. In dimension d = 2, necessary and sufficient conditions for stability are known, but fundamentally new phenomena arise in higher dimensions. Building on prior work by El Kharroubi, Ben Tahar and Yaacoubi [Stochastics Stochastics Rep. 68 (2000) 229–253, Math. Methods Oper. Res. 56 (2002) 243–258], we provide necessary and sufficient conditions for stability of SRBMs in three dimensions; to verify or refute these conditions is a simple computational task. As a byproduct, we find that the fluid-based criterion of Dupuis and Williams [Ann. Probab. 22 (1994) 680–702] is not only sufficient but also necessary for stability of SRBMs in three dimensions. That is, an SRBM in three dimensions is positive recurrent if and only if every path of the associated fluid model is attracted to the origin. The problem of recurrence classification for SRBMs in four and higher dimensions remains open.

In join the shortest queue networks, incoming jobs are assigned to the shortest queue from among a randomly chosen subset of D queues, in a system of N queues; after completion of service at its queue, a job leaves the network. We also assume that jobs arrive into the system according to a ratear α N Poisson process, α < 1, with rate-1 service at each queue. When the service at queues is exponentially distributed, it was shown in Vvedenskaya et al. [Probi. Inf. Transm. 32 (1996) 15-29] that the tail of the equilibrium queue size decays doubly exponentially in the limit as N → ∞. This is a substantial improvement over the case D = 1, where the queue size decays exponentially. The reasoning in [Probi. Inf. Transm. 32 (1996) 15-29] does not easily generalize to jobs with nonexponential service time distributions. A modularized program for treating general service time distributions was introduced in Bramson et al. [In Proc. ACM SIGMETRICS (2010) 275-286]. The program relies on an ansatz that asserts, in equilibrium, any fixed number of queues become independent of one another as N → ∞. This ansatz was demonstrated in several settings in Bramson et al. [Queueing Syst. 71 (2012) 247-292], including for networks where the service discipline is FIFO and the service time distribution has a decreasing hazard rate. In this article, we investigate the limiting behavior, as N → ∞, of the equilibrium at a queue when the service discipline is FIFO and the service time distribution has a power law with a given exponent — β, for β > 1. We show under the above ansatz that, as N → ∞, the tail of the equilibrium queue size exhibits a wide range of behavior depending on the relationship between β and D. In particular, if β > D/(D—1), the tail is doubly exponential and, if β < D/(D -1), the tail has a power law. When β = D/(D -1), the tail is exponentially distributed.

Semimartingale reflecting Brownian motions (SRBMs) are diffusion processes with state space the d -dimensional nonnegative orthant, in the interior of which the processes evolve according to a Brownian motion, and that reflect against the boundary in a specified manner. A standard problem is to determine under what conditions the process is positive recurrent. Necessary and sufficient conditions for positive recurrence are easy to formulate in d =2, but not in d ≥3. Fluid paths are solutions of deterministic equations that correspond to the random equations of the SRBM. A standard result of Dupuis and Williams (in Ann. Probab. 22:680–702, 1994 ) states that when every fluid path associated with the SRBM is attracted to the origin, the SRBM is positive recurrent. Employing this result, El Kharroubi et al. (in Stoch. Stoch. Rep. 68:229–253, 2000 ; Math. Methods Oper. Res. 56:243–258, 2002 ) gave sufficient conditions involving fluid paths for positive recurrence of SRBM in d =3. Here, we discuss two recent results regarding necessary conditions for positive recurrence of SRBM in d ≥3. Bramson et al. (in Ann. Appl. Probab. 20:753–783, 2010 ) showed that the conditions in El Kharroubi et al. (Math. Methods Oper. Res. 56:243–258, 2002 ) are, in fact, necessary in d =3. On the other hand, Bramson (in Ann. Appl. Probab., to appear, 2011 ) provided a family of positive recurrent SRBMs, in d ≥6, with linear fluid paths that diverge to infinity. The latter result shows in particular that the converse of the Dupuis–Williams result does not hold.

We consider a family of discrete time multihop switched queueing networks where each packet moves along a fixed route. In this setting, BackPressure is the canonical choice of scheduling policy; this policy has the virtues of possessing a maximal stability region and not requiring explicit knowledge of traffic arrival rates. BackPressure has certain structural weaknesses because implementation requires information about each route, and queueing delays can grow super-linearly with route length. For large networks, where packets over many routes are processed by a queue, or where packets over a route are processed by many queues, these limitations can be prohibitive. In this article, we introduce a scheduling policy for first-in, first-out networks, the ProportionalScheduler, which is based on the proportional fairness criterion. We show that, like BackPressure, the ProportionalScheduler has a maximal stability region and does not require explicit knowledge of traffic arrival rates. The ProportionalScheduler has the advantage that information about the network’s route structure is not required for scheduling, which substantially improves the policy’s performance for large networks. For instance, packets can be routed with only next-hop information and new nodes can be added to the network with only knowledge of the scheduling constraints.

In this paper we study the tightness of solutions for a family of recursion equations. These equations arise naturally in the study of random walks on tree-like structures. Examples include the maximal displacement of a branching random walk in one dimension and the cover time of a symmetric simple random walk on regular binary trees. Recursion equations associated with the distribution functions of these quantities have been used to establish weak laws of large numbers. Here, we use these recursion equations to establish the tightness of the corresponding sequences of distribution functions after appropriate centering. We phrase our results in a fairly general context, which we hope will facilitate their application in other settings.

The majority vote process was one of the first interacting particle systems to be investigated. It can be described briefly as follows. There are two possible opinions at each site of a graph G. At rate 1 − ε, the opinion at a site aligns with the majority opinion at its neighboring sites and, at rate ε, the opinion at a site is randomized due to noise, where ε ∈ [0, 1] is a parameter. Despite the simple dynamics of the majority vote process, its equilibrium behavior is difficult to analyze when the noise rate is small but positive. In particular, when the underlying graph is G = ℤⁿ with n ≥ 2, it is not known whether the process possesses more than one equilibrium. This is surprising, especially in light of the close analogy between this model and the stochastic Ising model, where much more is known. Here, we study themajority vote process on the infinite tree 𝕋 d with vertex degree d. For d ≥ 5 and small noise, we show that there are uncountably many mutually singular equilibria, with convergence to such an equilibrium occurring exponentially quickly from nearby initial states. Our methods are quite flexible and extend to a broader class of models, consensus processes. This class includes the stochastic Ising model and other processes in which the dynamics at a site depend on the number of neighbors holding a given opinion. All of our proofs are carried out in this broader context.