Explore the vast range of titles available.

We consider the stability of the longest-queue-first scheduling policy (LQF), a natural and low-complexity scheduling policy, for a generalized switch model. Unlike that of common scheduling policies, the stability of LQF depends on the variance of the arrival processes in addition to their average intensities. We identify new sufficient conditions for LQF to be throughput optimal for independent, identically distributed arrival processes. Deterministic fluid analogs, proved to be powerful in the analysis of stability in queueing networks, do not adequately characterize the stability of LQF. We combine properties of diffusion-scaled sample path functionals and local fluid limits into a sharper characterization of stability.

Understanding the Fundamentals of Empty-Car Routing in Ridesharing Systems How to efficiently route empty-cars in ridesharing systems? In this paper “Empty-car Routing in Ridesharing Systems,” A. Braverman, J.G. Dai, X. Liu, and L. Ying introduce a novel model based on closed queueing networks and propose an optimization framework to optimize empty-car routing for maximizing system-wide utility functions. We propose a fluid-based optimal routing policy by solving the optimization problem in a large market regime. We establish both process-level and steady-state convergence of the closed queueing network to the fluid-limit and prove the optimal network utility obtained from the fluid-based optimization is an upper bound on the utility in the finite car system for any routing policy under which the closed queueing network has a stationary distribution. This upper bound is achieved asymptotically under the fluid-based optimal routing policy. This paper considers a closed queueing network model of ridesharing systems, such as Didi Chuxing, Lyft, and Uber. We focus on empty-car routing, a mechanism by which we control car flow in the network to optimize system-wide utility functions, for example, the availability of empty cars when a passenger arrives. We establish both process-level and steady-state convergence of the queueing network to a fluid limit in a large market regime where demand for rides and supply of cars tend to infinity and use this limit to study a fluid-based optimization problem. We prove that the optimal network utility obtained from the fluid-based optimization is an upper bound on the utility in the finite car system for any routing policy, both static and dynamic, under which the closed queueing network has a stationary distribution. This upper bound is achieved asymptotically under the fluid-based optimal routing policy. Simulation results with real-world data released by Didi Chuxing demonstrate the benefit of using the fluid-based optimal routing policy compared with various other policies.

The performance of storage systems and database systems depends significantly on the page replacement policies. Although many page replacement policies have been discussed in the literature, their performances are not fully understood. We introduce analytical techniques for evaluating the performances of page replacement policies including two queue ( 2Q ), which manages two buffers to capture both the recency and frequency of requests. We derive an exact expression for the probability that a requested item is found (the hit probability) in a buffer managed by 2Q in the fluid limit, where the number of items is scaled by n , the size of items is scaled by 1/ n , and n approaches infinity. The hit probability in the fluid limit approximates the hit probability in the original system, and we find that the relative error in the approximation is typically within 1%. Our analysis also illuminates several fundamental properties of 2Q useful for system designers.

Randomized load balancing networks arise in a variety of applications, and allow for efficient sharing of resources, while being relatively easy to implement. We consider a network of parallel queues in which incoming jobs with independent and identically distributed service times are assigned to the shortest queue among a subset of d queues chosen uniformly at random, and leave the network on completion of service. Prior work on dynamical properties of this model has focused on the case of exponential service distributions. In this work, we analyze the more realistic case of general service distributions. We first introduce a novel particle representation of the state of the network, and characterize the state dynamics via a countable sequence of interacting stochastic measure-valued evolution equations. Under mild assumptions, we show that the sequence of scaled state processes converges, as the number of servers goes to infinity, to a hydrodynamic limit that is characterized as the unique solution to a countable system of coupled deterministic measure-valued equations. As a simple corollary, we also establish a propagation of chaos result that shows that finite collections of queues are asymptotically independent. The general framework developed here is potentially useful for analyzing a larger class of models arising in diverse fields including biology and materials science.

A shared ledger is a record of transactions that can be updated by any member of a group of users. The notion of independent and consistent record-keeping in a shared ledger is important for blockchain and more generally for distributed ledger technologies. In this paper we analyze a stochastic model for the shared ledger known as the tangle, which was devised as the basis for the IOTA cryptocurrency. The model is a random directed acyclic graph, and its growth is described by a non-Markovian stochastic process. We first prove ergodicity of the stochastic process, and then derive a delay differential equation for the fluid model which describes the tangle at high arrival rate. We prove convergence in probability of the tangle process to the fluid model, and also prove global stability of the fluid model. The convergence proof relies on martingale techniques.

We consider the supermarket model in the usual Markovian setting where jobs arrive at rate nλ n for some λ n > 0, with n parallel servers each processing jobs in its queue at rate 1. An arriving job joins the shortest among dn ≤ n randomly selected service queues. We show that when dn → ∞ and λ n → λ ∈ (0, ∞), under natural conditions on the initial queues, the state occupancy process converges in probability, in a suitable path space, to the unique solution of an infinite system of constrained ordinary differential equations parametrized by λ. Our main interest is in the study of fluctuations of the state process about its near equilibrium state in the critical regime, namely when λ n → 1. Previous papers, for example, (Stoch. Syst. 8 (2018) 265–292) have considered the regime d n n log n → ∞ while the objective of the current work is to develop diffusion approximations for the state occupancy process that allow for all possible rates of growth of dn . In particular, we consider the three canonical regimes (a) dn /√n → 0; (b) dn /√n → c ∈ (0, ∞) and, (c) dn /√n → ∞. In all three regimes, we show, by establishing suitable functional limit theorems, that (under conditions on λ n ) fluctuations of the state process about its near equilibrium are of order n −1/2 and are governed asymptotically by a one-dimensional Brownian motion. The forms of the limit processes in the three regimes are quite different; in the first case, we get a linear diffusion; in the second case, we get a diffusion with an exponential drift; and in the third case we obtain a reflected diffusion in a half space. In the special case dn /(√n log n) → ∞, our work gives alternative proofs for the universality results established in (Stoch. Syst. 8 (2018) 265–292).

A parallel server system with n identical servers is considered. The service time distribution has a finite mean 1 / μ, but otherwise is arbitrary. Arriving customers are routed to one of the servers immediately upon arrival. The join-idle-queue routeing algorithm is studied, under which an arriving customer is sent to an idle server, if such is available, and to a randomly uniformly chosen server, otherwise. We consider the asymptotic regime where n → ∞ and the customer input flow rate is λn. Under the condition λ / μ < ½, we prove that, as n → ∞, the sequence of (appropriately scaled) stationary distributions concentrates at the natural equilibrium point, with the fraction of occupied servers being constant at λ / μ. In particular, this implies that the steady-state probability of an arriving customer waiting for service vanishes.

Fractional-order epidemic models have become widely studied in the literature. Here, we consider the generalization of a simple SIR model in the context of generalized fractional calculus and we study the main features of such model. Moreover, we construct semi-Markov stochastic epidemic models by using time changed continuous time Markov chains, where the parent process is the stochastic analog of a simple SIR epidemic. In particular, we show that, differently from what happens in the classic case, the deterministic model does not coincide with the large population limit of the stochastic one. This loss of fluid limit is then stressed in terms of numerical examples.

The model is motivated by the problem of load distribution in large-scale cloud-based data processing systems. We consider a heterogeneous service system, consisting of multiple large server pools. The pools are different in that their servers may have different processing speeds and/or different buffer sizes (which may be finite or infinite). We study an asymptotic regime in which the customer arrival rate and pool sizes scale to infinity simultaneously, in proportion to some scaling parameter n . Arriving customers are assigned to the servers by a “router,” according to a pull-based algorithm, called PULL. Under the algorithm, each server sends a “pull-message” to the router, when it becomes idle; the router assigns an arriving customer to a server according to a randomly chosen available pull-message, if there are any, or to a random server, otherwise. Assuming subcritical system load, we prove asymptotic optimality of PULL. Namely, as system scale n → ∞ , the steady-state probability of an arriving customer experiencing blocking or waiting, vanishes. We also describe some generalizations of the model and PULL algorithm, for which the asymptotic optimality still holds.

A matching queue is described via a graph, an arrival process and a matching policy. Specifically, to each node in the graph there is a corresponding arrival process of items, which can either be queued or matched with queued items in neighboring nodes. The matching policy specifies how items are matched whenever more than one matching is possible. Given the matching graph and the matching policy, the stability region of the system is the set of intensities of the arrival processes rendering the underlying Markov process positive recurrent. In a recent paper, a condition on the arrival intensities, which was named Ncond, was shown to be necessary for the stability of a matching queue. That condition can be thought of as an analogue to the usual traffic condition for traditional queueing networks, and it is thus natural to study whether it is also sufficient. In this paper, we show that this is not the case in general. Specifically, we prove that, except for a particular class of graphs, there always exists a matching policy rendering the stability region strictly smaller than the set of arrival intensities satisfying Ncond. Our proof combines graph- and queueing-theoretic techniques: After showing explicitly, via fluid-limit arguments that the stability regions of two basic models is strictly included in Ncond, we generalize this result to any graph inducing either one of those two basic graphs.