Search

Pender, Rand and Wesson recently established a delay differential equation limit for a parallel service system with routing based on delayed information. We provide an interpretation of their scaling under which their limit can be regarded as an instance of a law of large numbers in the familiar many-server heavy-traffic scaling. It requires scaling in the probabilistic routing function. We also obtain related many-server heavy-traffic delay-differential-equation limits for more general models.

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 the growth of a model for the tangle, which is the shared ledger protocol used 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 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., 21 pages

In this paper, we study an $N$ server fork-join queue with nearly deterministic arrival and service times. Specifically, we present a fluid limit for the maximum queue length as $N\to\infty$. This fluid limit depends on the initial number of tasks. In order to prove these results, we develop extreme value theory and diffusion approximations for the queue lengths., 36 pages, 15 figures

We consider a multi-class multi-server retrial queueing system. Customers of each class arrive from outside the system according to a Poisson process. The service times for each class of customers are assumed to be exponentially distributed with service rates depending on both the customers’ class and the servers. We define the offered load and provide stability and instability conditions for this retrial queueing system. The stability result can be obtained by introducing artificial primitive processes and using the fluid limit approach.

We consider a variation of the processor-sharing (PS) queue, inspired by freelance job websites where multiple freelancers compete for a single job. We develop fluid limit approximations for the overloaded PS-model with multiple (possibly infinitely many) service stages. Based on this approximation, we estimate what proportion of freelancers get the job they apply for. In addition, the PS model studied here is an instance of PS with routing and impatience, for which no Lyapunov function is known, and we suggest some partial solutions.

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 purpose of this paper is to bridge kinetic plasma descriptions and low-frequency single-fluid models. More specifically, the asymptotics leading to magnetohydrodynamic regimes starting from the Vlasov–Maxwell system are investigated. The analogy with the derivation, from the Vlasov–Poisson system, of a fluid representation for ions coupled to the Boltzmann relation for electrons is also outlined. The aim is to identify asymptotic parameters explaining the transitions from one microscopic description to a macroscopic low-frequency model. These investigations provide groundwork for the derivation of multi-scale numerical methods, model coupling or physics-based preconditioning.

This paper focuses on the mechanism of Blocking Before Service (BBS), in time-varying many-server queues in tandem. BBS arises in telecommunication networks, production lines and healthcare systems. We model a stochastic tandem network under BBS and develop its corresponding fluid limit, which includes reflection due to jobs lost. Comparing our fluid model against simulation shows that the model is accurate and effective. This gives rise to design/operational insights regarding network throughput, under both BBS and BAS (Blocking After Service).

In this paper, we develop time-varying fluid models for tandem networks with blocking. Beyond having their own intrinsic value, these mathematical models are also limits of corresponding many-server stochastic systems. We begin by analyzing a two-station tandem network with a general time-varying arrival rate, a finite waiting room before the first station, and no waiting room between the stations. In this model, customers that are referred from the first station to the second when the latter is saturated (blocked) are forced to wait in the first station while occupying a server there. The finite waiting room before the first station causes customer loss and, therefore, requires reflection analysis. We then specialize our model to a single station (many-server fluid limit of the $$G_t/M/N/(N +H)$$ queue), generalize it to k stations in tandem, and allow finite internal waiting rooms. Our models yield operational insights into network performance, specifically on the effects of line length, bottleneck location, waiting room size, and the interaction among these effects.

We analyze a tractable model of a limit order book on short time scales, where the dynamics are driven by stochastic fluctuations between supply and demand. We establish the existence of a limiting distribution for the highest bid, and for the lowest ask, where the limiting distributions are confined between two thresholds. We make extensive use of fluid limits in order to establish recurrence properties of the model. We use the model to analyze various high-frequency trading strategies, and comment on the Nash equilibria that emerge between high-frequency traders when a market in continuous time is replaced by frequent batch auctions., Revision of the submitted version: correcting an error (caught by Jan Swart) in the statement of Proposition 4.1 (1), propagating to Theorem 2.1 (1)

We consider the model of a token-based joint auto-scaling and load balancing strategy, proposed in a recent paper by Mukherjee, Dhara, Borst, and van Leeuwaarden [4] (SIGMETRICS '17), which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers N ! 1. In the above work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buffers, and therefore the fundamental question of stability of the proposed scheme with infinite buffers was left open. In this paper, we address this fundamental stability question. The system stability under the usual subcritical load assumption is not automatic. Moreover, the stability may not even hold for all N. The key challenge stems from the fact that the process lacks monotonicity, which has been the powerful primary tool for establishing stability in load balancing models. We develop a novel method to prove that the subcritically loaded system is stable for large enough N, and establish convergence of steady-state distributions to the optimal one, as N ! 1. The method goes beyond the state of the art techniques " it uses an induction-based idea and a "weak monotonicity" property of the model; this technique is of independent interest and may have broader applicability.

We consider two players, starting with $m$ and $n$ units, respectively. In each round, the winner is decided with probability proportional to each player's fortune, and the opponent loses one unit. We prove an explicit formula for the probability $p(m,n)$ that the first player wins. When $m\sim Nx_{0}$, $n\sim N y_{0}$, we prove the fluid limit as $N\to \infty$. When $x_{0}=y_{0}$, then $z\to p(N,N+z\sqrt{N})$ converges to the standard normal CDF and the difference in fortunes scales diffusively. The exact limit of the time of ruin $\tau_{N}$ is established as $(T-\tau_N) \sim N^{-\beta}W^{\frac{1}{\beta}}$, $\beta=\frac{1}{4}$, $T=x_{0}+y_{0}$. Modulo a constant, $W \sim \chi^{2}_{1}(z_{0}^{2}/T^{2})$., Comment: 34 pages

We introduce a new framework for the analysis of large-scale load balancing networks with general service time distributions, motivated by applications in server farms, distributed memory machines, cloud computing and communication systems. For a parallel server network using the so-called $SQ(d)$ load balancing routing policy, we use a novel representation for the state of the system and identify its fluid limit, when the number of servers goes to infinity and the arrival rate per server tends to a constant. The fluid limit is characterized as the unique solution to a countable system of coupled partial differential equations (PDE), which serve to approximate transient Quality of Service parameters such as the expected virtual waiting time and queue length distribution. In the special case when the service time distribution is exponential, our method recovers the well-known ordinary differential equation characterization of the fluid limit. Furthermore, we develop a numerical scheme to solve the PDE, and demonstrate the efficacy of the PDE approximation by comparing it with Monte Carlo simulations. We also illustrate how the PDE can be used to gain insight into the performance of large networks in practical scenarios by analyzing relaxation times in a backlogged network. In particular, our numerical approximation of the PDE uncovers two interesting properties of relaxation times under the SQ(2) algorithm. Firstly, when the service time distribution is Pareto with unit mean, the relaxation time decreases as the tail becomes heavier. This is a priori counterintuitive given that for the Pareto distribution, heavier tails have been shown to lead to worse tail behavior in equilibrium. Secondly, for unit mean light-tailed service distributions such as the Weibull and lognormal, the relaxation time decreases as the variance increases. This is in contrast to the behavior observed under random routing, where the relaxation time increases with increase in variance.

We consider load balancing in service systems with affinity relations between jobs and servers. Specifically, an arriving job can be assigned to a fast, primary server from a particular selection associated with this job or to a secondary server to be processed at a slower rate. Such job–server affinity relations can model network topologies based on geographical proximity, or data locality in cloud scenarios. We introduce load balancing schemes that assign jobs to primary servers if available, and otherwise to secondary servers. A novel coupling construction is developed to obtain stability conditions and performance bounds. We also conduct a fluid limit analysis for symmetric model instances, which reveals a delicate interplay between the model parameters and load balancing performance.

We study a single server queue under a processor-sharing type of scheduling policy, where the weights for determining the sharing are given by functions of each job's remaining service (processing) amount, and obtain a fluid limit for the scaled measure-valued system descriptors.

We study ergodic properties of a class of Markov-modulated general birth-death processes under fast regime switching. The first set of results concerns the ergodic properties of the properly scaled joint Markov process with a parameter that is taken large. Under very weak hypotheses, we show that if the averaged process is exponentially ergodic for large values of the parameter, then the same applies to the original joint Markov process. The second set of results concerns steady-state diffusion approximations, under the assumption that the 'averaged' fluid limit exists. Here, we establish convergence rates for the moments of the approximating diffusion process to those of the Markov modulated birth-death process. This is accomplished by comparing the generator of the approximating diffusion and that of the joint Markov process. We also provide several examples which demonstrate how the theory can be applied., 23 pages

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 randomly chosen subset of $d$ queues, 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 sequence of interacting measure-valued stochastic processes. 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. 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., Comment: 71 pages, Extended version

Load balancing algorithms play a vital role in enhancing performance in data centers and cloud networks. Due to the massive size of these systems, scalability challenges, and especially the communication overhead associated with load balancing mechanisms, have emerged as major concerns. Motivated by these issues, we introduce and analyze a novel class of load balancing schemes where the various servers provide occasional queue updates to guide the load assignment. We show that the proposed schemes strongly outperform JSQ( d ) strategies with comparable communication overhead per job, and can achieve a vanishing waiting time in the many-server limit with just one message per job, just like the popular JIQ scheme. The proposed schemes are particularly geared however towards the sparse feedback regime with less than one message per job, where they outperform corresponding sparsified JIQ versions. We investigate fluid limits for synchronous updates as well as asynchronous exponential update intervals. The fixed point of the fluid limit is identified in the latter case, and used to derive the queue length distribution. We also demonstrate that in the ultra-low feedback regime the mean stationary waiting time tends to a constant in the synchronous case, but grows without bound in the asynchronous case.

The purpose of this note is to show that it is possible to establish a many-server functional strong law of large numbers (FSLLN) for the fraction of occupied servers (i.e., the scaled number-in-system) without explicitly tracking through a measure valued process either the age or the residual service times of the jobs in a non-Markovian, non-stationary loss model. This considerable analytical simplification is achieved by exploiting a semimartingale representation. The fluid limit is shown to be the unique solution of a Volterra integral equation.

In this paper, we establish a fluid limit for a two-sided Markov order book model. The main result states that in a certain asymptotic regime, a pair of measure-valued processes representing the “sell-side shape” and “buy-side shape” of an order book converges to a pair of deterministic measure-valued processes in a certain sense. We also test the fluid approximation on data. The empirical results suggest that the approximation is reasonably good for liquidly traded stocks in certain time periods.

A single queueing station serving K input streams with renewal arrivals and generally distributed independent and identically distributed service times is considered. Customers are served by the Shortest Remaining Processing Time policy. In the case of a tie, the first-in, first-out policy is utilized. We analyze a fluid model for the evolution of a measure-valued state descriptor of this system, with particular emphasis on its limiting behavior in the critical case as time gets large. We also prove a fluid limit theorem justifying our fluid model as the first-order approximation of the queueing system under consideration. Along the way, we establish fluid limits for the corresponding state-dependent response times.

The backpressure scheduling algorithm for multihop wireless networks is known to be throughput optimal, but it requires each node to maintain per-destination queues. Recently, a clever generalization of processor sharing has been proposed which is also throughput optimal, but which only uses per-link queues. Here, we propose another algorithm, called Queue-Proportional Rate Allocation (QPRA), which also only uses per-link queues and allocates service rates to links in proportion to their queue lengths, and employs the Serve-In-Random-Order queueing discipline within each link. Through fluid limit techniques and using a novel Lyapunov function, we show that the QPRA algorithm achieves the maximum throughput. We demonstrate an advantage of QPRA by showing that, for the so-called primary interference model, it is able to develop a low-complexity scheduling scheme which approximates QPRA and achieves a constant fraction of the maximum throughput region, independent of network size.

We consider the following distributed service model: jobs with unit mean, exponentially distributed, and independent processing times arrive as a Poisson process of rate $\lambda n$, with $00$ (no matter how small), if our policy only uses a linear message rate $\alpha n$, the resulting asymptotic delay is upper bounded, uniformly over all $\lambda

This work is devoted to the numerical simulation of the \BGK equation for two species in the fluid limit using a particle method. Thus, we are interested in a gas mixture consisting of two species without chemical reactions assuming that the number of particles of each species remains constant. We consider the kinetic two species model proposed by Klingenberg, Pirner and Puppo in 2017, which separates the intra and interspecies collisions. We want to study numerically the influence of the two relaxation term, one corresponding to intra, the other to interspecies collisions. For this, we use the method of micro-macro decomposition. First, we derive an equivalent model based on the micro-macro decomposition (see Bennoune, Lemou and Mieussens, 2007 and Crestetto, Crouseilles and Lemou, 2013). The kinetic micro part is solved by a particle method, whereas the fluid macro part is discretized by a standard finite volume scheme. Main advantages of this approach are: (i) the noise inherent to the particle method is reduced compared to a standard (without micro-macro decomposition) particle method, (ii) the computational cost of the method is reduced in the fluid limit since a small number of particles is then sufficient.

There is a growing interest in development of in-network dispersed computing paradigms that leverage the computing capabilities of heterogeneous resources dispersed across the network for processing massive amount of data is collected at the edge of the network. We consider the problem of task scheduling for such networks, in a dynamic setting in which arriving computation jobs are modeled as chains, with nodes representing tasks, and edges representing precedence constraints among tasks. In our proposed model, motivated by significant communication costs in dispersed computing environments, the communication times are taken into account. More specifically, we consider a network where servers are capable of serving all task types, and sending the results of processed tasks from one server to another server results in some communication delay that makes the design of optimal scheduling policy significantly more challenging than classical queueing networks. As the main contributions of the paper, we first characterize the capacity region of the network, then propose a novel virtual queueing network encoding the state of the network. Finally, we propose a Max-Weight type scheduling policy, and considering the virtual queueing network in the fluid limit, we use a Lyapunov argument to show that the policy is throughput-optimal., accepted to appear in IEEE/ACM Transactions on Networking

We consider the model of a token-based joint auto-scaling and load balancing strategy, proposed in a recent paper by Mukherjee, Dhara, Borst, and van Leeuwaarden (SIGMETRICS '17, arXiv:1703.08373), which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers $N\to\infty$. In the above work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buffers, and therefore the fundamental question of stability of the proposed scheme with infinite buffers was left open. In this paper, we address this fundamental stability question. The system stability under the usual subcritical load assumption is not automatic. Moreover, the stability may not even hold for all $N$. The key challenge stems from the fact that the process lacks monotonicity, which has been the powerful primary tool for establishing stability in load balancing models. We develop a novel method to prove that the subcritically loaded system is stable for large enough $N$, and establish convergence of steady-state distributions to the optimal one, as $N \to \infty$. The method goes beyond the state of the art techniques -- it uses an induction-based idea and a "weak monotonicity" property of the model; this technique is of independent interest and may have broader applicability., 30 pages

In multi-server distributed queueing systems, the access of stochastically arriving jobs to resources is often regulated by a dispatcher, also known as load balancer. A fundamental problem consists in designing a load balancing algorithm that minimizes the delays experienced by jobs. During the last two decades, the power-of-$d$-choice algorithm, based on the idea of dispatching each job to the least loaded server out of $d$ servers randomly sampled at the arrival of the job itself, has emerged as a breakthrough in the foundations of this area due to its versatility and appealing asymptotic properties. In this paper, we consider the power-of-$d$-choice algorithm with the addition of a local memory that keeps track of the latest observations collected over time on the sampled servers. Then, each job is sent to a server with the lowest observation. We show that this algorithm is asymptotically optimal in the sense that the load balancer can always assign each job to an idle server in the large-system limit. This holds true if and only if the system load $\lambda$ is less than $1-\frac{1}{d}$. If this condition is not satisfied, we show that queue lengths are tightly bounded by $\left\lceil - \frac{ \log (1-\lambda)}{\log (\lambda d +1)} \right\rceil$. This is in contrast with the classic version of the power-of-$d$-choice algorithm, where at the fluid scale a strictly positive proportion of servers containing $i$ jobs exists for all $i\ge 0$, in equilibrium. Our results quantify and highlight the importance of using memory as a means to enhance performance in randomized load balancing.

We develop diffusion approximations for parallel-queueing systems with the randomized longest-queue-first scheduling (LQF) algorithm by establishing new mean-field limit theorems as the number of buffers n → ∞. We achieve this by allowing the number of sampled buffers d = d(n) to depend on the number of buffers n, which yields an asymptotic 'decoupling' of the queue length processes. We show through simulation experiments that the resulting approximation is accurate even for moderate values of n and d(n). To the best of the authors' knowledge, this is the first derivation of diffusion approximations for a queueing system in the large-buffer mean-field regime. Another noteworthy feature of our scaling idea is that the randomized LQF algorithm emulates the LQF algorithm, yet is computationally more attractive. The analysis of the system performance as a function of d(n) is facilitated by the multi-scale nature in our limit theorems: the various processes we study have different space scalings. This allows us to show the trade-off between performance and complexity of the randomized LQF scheduling algorithm.

We consider a system of N parallel queues with unit exponential service rates and a single dispatcher where tasks arrive as a Poisson process of rate λ( N ). When a task arrives, the dispatcher assigns it to a server with the shortest queue among d ( N ) ≤ N randomly selected servers. This load balancing policy is referred to as a power-of- d ( N ) or JSQ( d ( N )) scheme, and subsumes the Join-the-Shortest Queue (JSQ) policy as a crucial special case for d ( N ) = N . We construct a coupling to bound the difference in the queue length processes between the JSQ policy and an arbitrary value of d ( N ). We use the coupling to derive the fluid limit in the regime where λ( N )/ N → λ < 1 and d ( N )→ ∞ as N → ∞, along with the corresponding fixed point. The fluid limit turns out not to depend on the exact growth rate of d ( N ), and in particular coincides with that for the JSQ policy. We further leverage the coupling to establish that the diffusion limit in the regime where ( N --λ( N ))/ √ N → β > 0 and d ( N )/ √ N log N → ∞ as N → ∞ corresponds to that for the JSQ policy. These results indicate that the stochastic optimality of the JSQ policy can be preserved at the fluid-level and diffusion-level while reducing the overhead by nearly a factor O( N ) and O(√ N ), respectively.

Bike sharing systems have rapidly developed around the world, and they are served as a promising strategy to improve urban traffic congestion and to decrease polluting gas emissions. So far performance analysis of bike sharing systems always exists many difficulties and challenges under some more general factors. In this paper, a more general large-scale bike sharing system is discussed by means of heavy traffic approximation of multiclass closed queueing networks with non-exponential factors. Based on this, the fluid scaled equations and the diffusion scaled equations are established by means of the numbers of bikes both at the stations and on the roads, respectively. Furthermore, the scaling processes for the numbers of bikes both at the stations and on the roads are proved to converge in distribution to a semimartingale reflecting Brownian motion (SRBM) in a \(N^{2}\)-dimensional box, and also the fluid and diffusion limit theorems are obtained. Furthermore, performance analysis of the bike sharing system is provided. Thus the results and methodology of this paper provide new highlight in the study of more general large-scale bike sharing systems.

In this work, the fluid limit approach methodology is applied to find a sufficient and necessary stability condition for the Basic Collaboration (BC) system with feedback allowed, which is a generalization of the so-called W-model. In this queueing system, some customer classes need cooperation of a subset of (non-overlapping) servers. We assume that each customer class arrives to the system following a renewal input with general i.i.d. inter-arrival times, and general i.i.d. service times are also assumed. Priority is given to customer classes that can not be served by a single server but need a cooperation.

The synchronization process inherent to the Bitcoin network gives rise to an infinite-server model with the unusual feature that customers interact. Among the closed-form characteristics that we derive for this model is the busy period distribution which, counterintuitively, does not depend on the arrival rate. We explain this by exploiting the equivalence between two specific service disciplines, which is also used to derive the model's stationary distribution. Next to these closed-form results, the second major contribution concerns an asymptotic result: a fluid limit in the presence of service delays. Since fluid limits arise under scalings of the law-of-large-numbers type, they are usually deterministic, but in the setting of the model discussed in this paper the fluid limit is random (more specifically, of growth-collapse type)., Comment: 23 pages, 3 figures

In the present paper, we study the evolution of an overloaded cyclic polling model that starts empty. Exploiting a connection with multitype branching processes, we derive fluid asymptotics for the joint queue length process. Under passage to the fluid dynamics, the server switches between the queues infinitely many times in any finite time interval causing frequent oscillatory behavior of the fluid limit in the neighborhood of zero. Moreover, the fluid limit is random. Additionally, we suggest a method that establishes finiteness of moments of the busy period in an M/G/1 queue., Comment: 36 pages, 2 pictures

Fluid or mean-field methods are approximate analytical techniques which have proven effective in tackling the infamous state-space explosion problem which typically arises when modelling large-scale concurrent systems based on interleaving semantics. These methods are particularly suitable in situations which present large populations of simple interacting objects characterised by small local state spaces, since they require the analysis of a problem which is insensitive to the population sizes but is dependent only on the size of the local state spaces. This paper studies the case when the replicated objects are best described as composites which consist of smaller simple objects. A congenial formal modelling framework for situations of this kind may be given by stochastic process algebra. Using PEPA as a representative case, we find that fluid models with replicated copies of composite processes do not scale well with increasing population sizes, thus rendering intractable the analysis of the underlying system of ordinary differential equations (ODEs). We call this problem continuous state-space explosion, by analogy with its counterpart phenomenon in discrete state spaces. The main contribution of this paper is a result of equivalence that simplifies, in an exact way, the potentially massive ODE system arising in those circumstances to one whose size is independent from all the multiplicities in the model. As a byproduct, we find that these simplified ODEs turn out to characterise the fluid behaviour of a family of PEPA models whose elements cannot be related to each other through any known equivalence relation. A substantial numerical assessment investigates the relationship between the different underlying Markov chains and their unique fluid limit, demonstrating its generally good accuracy for all practical purposes.

In the context of load balancing, Lu et al. introduced the distributed Join-Idle-Queue algorithm, where a group of dispatchers distribute jobs to a cluster of parallel servers. Each dispatcher maintains a queue of idle servers; when a job arrives to a dispatcher, it sends it to a server on its queue, or to a random server if the queue is empty. In turn, when a server has no jobs, it requests to be placed on the idle queue of a randomly chosen dispatcher. Although this algorithm was shown to be quite effective, the original asymptotic analysis makes simplifying assumptions that become increasingly inaccurate as the system load increases. Further, the analysis does not naturally generalize to interesting variations, such as having a server request to be placed on the idle queue of a dispatcher before it has completed all jobs, which can be beneficial under high loads. We provide a new asymptotic analysis of Join-Idle-Queue systems based on mean field fluid limit methods, deriving families of differential equations that describe these systems. Our analysis avoids previous simplifying assumptions, is empirically more accurate, and generalizes naturally to the variation described above, as well as other simple variations. Our theoretical and empirical analyses shed further light on the performance of Join-Idle-Queue, including potential performance pitfalls under high load., 11 pages, draft paper, likely to be at Allerton 2016, possibly improved before then

A parallel server system with $n$ identical servers is considered. The service time distribution has a finite mean $1/\mu$, but otherwise is arbitrary. Arriving customers are be routed to one of the servers immediately upon arrival. Join-Idle-Queue routing 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\to\infty$ and the customer input flow rate is $\lambda n$. Under the condition $\lambda/\mu, Comment: Revision. 11 pages

We consider a system of N identical parallel server pools and a single dispatcher where tasks arrive as a Poisson process. Arriving tasks cannot be queued, and must immediately be assigned to one of the server pools to start execution. The execution times are assumed to be exponentially distributed, and do not depend on the number of tasks contending for service. However, the experienced performance (e.g. in terms of received throughput or packet-level delay) does degrade with an increasing number of concurrent tasks at the same server pool. In order to optimize the performance, the dispatcher therefore aims to evenly distribute the tasks across the various server pools, using either a power-of-d or a threshold-based load balancing scheme. In the power-of-d scheme, an arriving task is assigned to the server pool with the minimum number of active tasks among d(N) randomly selected server pools (1 ≤ d(N) ≤ N). In the threshold-based scheme, an incoming task is dispatched to an arbitrary server pool with fewer than L active tasks, if there is any, to an arbitrary server pool with fewer than H > L tasks otherwise, or to a randomly selected server pool if all server pools have H or more tasks. This scheme can be implemented in a server-driven manner, with O(1) communication overhead per task, as opposed to O(d(N)) in the power-of-d scheme. We derive the fluid-level dynamics for the power-of-d scheme with d(N) → ∞ as N → ∞ and the threshold-based scheme, along with the associated fixed points. As it turns out, the fluid limit for the power-of-d scheme does not depend on the exact growth rate of d(N). We also characterize the diffusion-level behavior of the power-of-d scheme with d(N) ≫ √N log(N), and show that it coincides with that of the threshold-based scheme with suitably selected parameters L and H. In particular, the threshold-based scheme can achieve similar performance as the power-of-d scheme with d(N) ≫ √N log(N), and thus diffusion-level optimality, with only O(1) rather than O(N) communication overhead per task.

We study a system, where a random flow of customers is served by servers (called agents) invited on-demand. Each invited agent arrives into the system after a random time; after each service completion, an agent returns to the system or leaves it with some fixed probabilities. Customers and/or agents may be impatient, that is, while waiting in queue, they leave the system at a certain rate (which may be zero). We consider the queue-length-based feedback scheme, which controls the number of pending agent invitations, depending on the customer and agent queue lengths and their changes. The basic objective is to minimize both customer and agent waiting times. We establish the system process fluid limits in the asymptotic regime where the customer arrival rate goes to infinity. We use the machinery of switched linear systems and common quadratic Lyapunov functions to approach the stability of fluid limits at the desired equilibrium point, and derive a variety of sufficient local stability conditions. For our model, we conjecture that local stability is in fact sufficient for global stability of fluid limits; the validity of this conjecture is supported by numerical and simulation experiments. When local stability conditions do hold, simulations show good overall performance of the scheme., Comment: arXiv admin note: substantial text overlap with arXiv:1603.03413

We consider a system of $N$ parallel single-server queues with unit exponential service rates and a single dispatcher where tasks arrive as a Poisson process of rate $\lambda(N)$. When a task arrives, the dispatcher assigns it to a server with the shortest queue among $d(N)$ randomly selected servers ($1 \leq d(N) \leq N$). This load balancing strategy is referred to as a JSQ($d(N)$) scheme, marking that it subsumes the celebrated Join-the-Shortest Queue (JSQ) policy as a crucial special case for $d(N) = N$. We construct a stochastic coupling to bound the difference in the queue length processes between the JSQ policy and a scheme with an arbitrary value of $d(N)$. We use the coupling to derive the fluid limit in the regime where $\lambda(N) / N \to \lambda < 1$ as $N \to \infty$ with $d(N) \to\infty$, along with the associated fixed point. The fluid limit turns out not to depend on the exact growth rate of $d(N)$, and in particular coincides with that for the JSQ policy. We further leverage the coupling to establish that the diffusion limit in the critical regime where $(N - \lambda(N)) / \sqrt{N} \to \beta > 0$ as $N \to \infty$ with $d(N)/(\sqrt{N} \log (N))\to\infty$ corresponds to that for the JSQ policy. These results indicate that the optimality of the JSQ policy can be preserved at the fluid-level and diffusion-level while reducing the overhead by nearly a factor O($N$) and O($\sqrt{N}/\log(N)$), respectively., Comment: 39 pages, 2 figures, companion paper of arXiv:1612.00722

We consider a service system where agents (or, servers) are invited on-demand. Customers arrive as a Poisson process and join a customer queue. Customer service times are i.i.d. exponential. Agents' behavior is random in two respects. First, they can be invited into the system exogenously, and join the agent queue after a random time. Second, with some probability they rejoin the agent queue after a service completion, and otherwise leave the system. The objective is to design a real-time adaptive agent invitation scheme that keeps both customer and agent queues/waiting-times small. We study an adaptive scheme, which controls the number of pending agent invitations, based on queue-state feedback. We study the system process fluid limits, in the asymptotic regime where the customer arrival rate goes to infinity. The fluid limit trajectories have complicated behavior -- there are two domains where they follow different ODEs, and a "reflecting" boundary. We use the machinery of switched linear systems and common quadratic Lyapunov functions to approach the stability of fluid limits at the desired equilibrium point (with zero queues). We derive sufficient local stability conditions for the fluid limits. We conjecture that, for our model, local stability is in fact sufficient for global stability of fluid limits; the validity of this conjecture is supported by numerical and simulation experiments. When the local stability conditions do hold, simulations show good overall performance of the scheme., Comment: arXiv admin note: text overlap with arXiv:1409.7380

International audience; We study the dynamics of opinion propagation in a medium-sized population with low population turnover. Opinion spreading is modelled by a Markovian non-standard Susceptible-Infected-Recovered (SIR) epidemic model with stochastic arrivals, departures, infections and recoveries. The system performance is evaluated by two complementary approaches: a numerical but approximate solution approach which relies on Maclaurin-series expansions of the stationary solution of the Markov process and a fluid limit approach. Both methods are evaluated numerically. Moreover, convergence to the fluid limit is proved, and explicit expressions for the fixed points of the differential equations are obtained for the case of linearly increasing infection and arrival rates.

We study the stochastic diffusive limit of a kinetic radiative transfer equation, which is non-linear, involving a small parameter and perturbed by a smooth random term. Under an appropriate scaling for the small parameter, using a generalization of the perturbed test-functions method, we show the convergence in law to a stochastic non-linear fluid limit., Comment: 24 pages. arXiv admin note: text overlap with arXiv:1311.4743

Routing mechanisms for stochastic networks are often designed to produce state space collapse (SSC) in a heavy-traffic limit, i.e., to confine the limiting process to a lower-dimensional subset of its full state space. In a fluid limit, a control producing asymptotic SSC corresponds to an ideal sliding mode control that forces the fluid trajectories to a lower-dimensional sliding manifold. Within deterministic dynamical systems theory, it is well known that sliding-mode controls can cause the system to chatter back and forth along the sliding manifold due to delays in activation of the control. For the prelimit stochastic system, chattering implies fluid-scaled fluctuations that are larger than typical stochastic fluctuations. In this paper we show that chattering can occur in the fluid limit of a controlled stochastic network when inappropriate control parameters are used. The model has two large service pools operating under the fixed-queue-ratio with activation and release thresholds (FQR-ART) overload control which we proposed in a recent paper. The FQR-ART control is designed to produce asymptotic SSC by automatically activating sharing (sending some customers from one class to the other service pool) once an overload occurs. We have previously shown that this control is effective and robust, even if the service rates are less for the other shared customers, when the control parameters are chosen properly. We now show that, if the control parameters are not chosen properly, then delays in activating and releasing the control can cause chattering with large oscillations in the fluid limit. In turn, these fluid-scaled fluctuations lead to severe congestion, even when the arrival rates are smaller than the potential total service rate in the system, a phenomenon referred to as congestion collapse. We show that the fluid limit can be a bi-stable switching system possessing a unique nontrivial periodic equilibrium, in addition to a unique stationary point.

Cloud computing is a new paradigm where a company makes money by selling computing resources including both software and hardware. The core part or infrastructure of cloud computing is the data center where a large number of servers are available for processing incoming data traffic. These servers not only consume a large amount of energy to process data, but also need a large amount of energy to keep cool. Therefore, a reduction of a few percent of the power consumption means saving a substantial amount of money for the company as well as reduce our impact on the environment. As it currently stands, an idle server still consumes about 60 % of its peak energy usage. Thus, a natural suggestion to reduce energy consumption is to turn off servers which are not processing data. However, turning off servers can affect the customer experience. Customers trying to access computing power will experience delays if their data cannot be processed quickly enough. Moreover, servers require setup times in order to move from the off state to the on state. In the setup phase, servers consume energy, but cannot process data. Therefore, there exists a trade-off between power consumption and delay performance. In [7, 9], the authors analyze this tradeoff using an M/M/c queue with setup time for which they present a decomposition property by solving difference equations. In this paper, we complement recent stationary analysis of these types of models by studying the sample path behavior of the queueing model. In this regard, we prove a weak law of large numbers or fluid limit theorem for the queue length and server processes as the number of arrivals and number of servers tends to infinity. This methodology allows us to consider the impact of nonstationary arrivals and abandonment, which have not been considered in the literature so far.

We consider a framework for solving optimal liquidation problems in limit order books. In particular, order arrivals are modeled as a point process whose intensity depends on the liquidation price. We set up a stochastic control problem in which the goal is to maximize the expected revenue from liquidating the entire position held. We solve this optimal liquidation problem for power-law and exponential-decay order book models explicitly and discuss several extensions. We also consider the continuous selling (or fluid) limit when the trading units are ever smaller and the intensity is ever larger. This limit provides an analytical approximation to the value function and the optimal solution. Using techniques from viscosity solutions we show that the discrete state problem and its optimal solution converge to the corresponding quantities in the continuous selling limit uniformly on compacts.

We consider a single-server queue with renewal arrivals and i.i.d. service times, in which the server employs either the preemptive Shortest Remaining Processing Time (SRPT) policy, or its non-preemptive variant, Shortest Job First (SJF). We show that for given stochastic primitives (initial condition, arrival and service processes), the model has the same fluid limit under either policy. In particular, we conclude that the well-known queue length optimality of preemptive SRPT is also achieved, asymptotically on fluid scale, by the simpler-to-implement SJF policy. We also conclude that on fluid scale, SJF and SRPT achieve the same performance with respect to state-dependent response times.

We introduce a formal limit, which we refer to as a fluid limit, of scaled stochastic models for a cache managed with the least-recently-used algorithm when requests are issued according to general stochastic point processes. We define our fluid limit as a superposition of dependent replications of the original system with smaller item sizes when the number of replications approaches ∞. We derive the average probability that a requested item is not in a cache (average miss probability) in the fluid limit. We show that, when requests follow inhomogeneous Poisson processes, the average miss probability in the fluid limit closely approximates that in the original system. Also, we compare the asymptotic characteristics, as the cache size approaches ∞, of the average miss probability in the fluid limit to those in the original system.

We derive rough and exact asymptotic expressions for the stationary distributionπ of a Markov chain arising in a queueing/production context. The approachwe develop can also handle "cascades," which are situations where the fluid limit ofthe large deviation path from the origin to the increasingly rare event is nonlinear. Ourapproach considers a process that starts at the rare event. In our production example,we can have two sequences of states that asymptotically lie on the same line, yet πhas different asymptotics on the two sequences.

Partially ionized plasmas corresponding to different ionization degrees are derived and connected one with each other by the diffusion approximation methodology. These plasmas are the following electrical discharges: a thermal arc discharge, glow discharges in local thermodynamic equilibrium -LTE- and in non-LTE, and a non-LTE glow discharge interacting with an electron beam (or flow).

With double hashing, for a key $x$, one generates two hash values $f(x)$ and $g(x)$, and then uses combinations $(f(x) +i g(x)) \bmod n$ for $i=0,1,2,...$ to generate multiple hash values in the range $[0,n-1]$ from the initial two. For balanced allocations, keys are hashed into a hash table where each bucket can hold multiple keys, and each key is placed in the least loaded of $d$ choices. It has been shown previously that asymptotically the performance of double hashing and fully random hashing is the same in the balanced allocation paradigm using fluid limit methods. Here we extend a coupling argument used by Lueker and Molodowitch to show that double hashing and ideal uniform hashing are asymptotically equivalent in the setting of open address hash tables to the balanced allocation setting, providing further insight into this phenomenon. We also discuss the potential for and bottlenecks limiting the use this approach for other multiple choice hashing schemes., 13 pages ; current draft ; will be submitted to conference shortly