Search

Inaccuracies in the initial conditions for cosmological N-body simulations could easily be the largest source of systematic error in predicting the non-linear large-scale structure. From the theory side, initial conditions are usually provided by using low-order truncations of the displacement field from Lagrangian perturbation theory, with the first and second-order approximations being the most common ones. Here we investigate the improvement brought by using initial conditions based on third-order Lagrangian perturbation theory (3LPT). We show that with 3LPT, truncation errors are vastly suppressed, thereby opening the portal to initializing simulations accurately as late as z=12 (for the resolution we consider). We analyse the competing effects of perturbative truncation and particle discreteness on various summary statistics. Discreteness errors are essentially decaying modes and thus get strongly amplified for earlier initialization times. We show that late starting times with 3LPT provide the most accurate configuration, which we find to coincide with the continuum fluid limit within 1 per cent for the power- and bispectrum at z=0 up to the particle Nyquist wave number of our simulations (k ~ 3h/Mpc). In conclusion, to suppress non-fluid artefacts, we recommend initializing simulations as late as possible with 3LPT. We make our 3LPT initial condition generator publicly available., Comment: 22 pages, 13 figures, minor revisions (matches published version), code available from https://bitbucket.org/ohahn/monofonic

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 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 consider a simple stochastic model for the spread of a disease caused by two virus strains in a closed homogeneously mixing population of size N. The spread of each strain in the absence of the other one is described by the stochastic logistic SIS epidemic process, and we assume that there is perfect cross-immunity between the two strains, that is, individuals infected by one are temporarily immune to re-infections and infections by the other. For the case where one strain has a strictly larger basic reproductive ratio than the other, and the stronger strain on its own is supercritical (that is, its basic reproductive ratio is larger than 1), we derive precise asymptotic results for the distribution of the time when the weaker strain disappears from the population, that is, its extinction time. We further extend our results to certain parameter values where the difference between the two reproductive ratios may tend to 0 as $N \to \infty$. In proving our results, we illustrate a new approach to a fluid limit approximation for a sequence of Markov chains in the vicinity of a stable fixed point of the limit., Comment: 53 pages

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

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; The ad-trading desks of media-buying agencies are increasingly relying on complex algorithms for purchasing advertising inventory. In particular, Real-Time Bidding (RTB) algorithms respond to many auctions -- usually Vickrey auctions -- throughout the day for buying ad-inventory with the aim of maximizing one or several key performance indicators (KPI). The optimization problems faced by companies building bidding strategies are new and interesting for the community of applied mathematicians. In this article, we introduce a stochastic optimal control model that addresses the question of the optimal bidding strategy in various realistic contexts: the maximization of the inventory bought with a given amount of cash in the framework of audience strategies, the maximization of the number of conversions/acquisitions with a given amount of cash, etc. In our model, the sequence of auctions is modeled by a Poisson process and the \textit{price to beat} for each auction is modeled by a random variable following almost any probability distribution. We show that the optimal bids are characterized by a Hamilton-Jacobi-Bellman equation, and that almost-closed form solutions can be found by using a fluid limit. Numerical examples are also carried out.

We consider a general class of preferential attachment schemes evolving by a reinforcement rule with respect to certain sublinear weights. In these schemes, which grow a random network, the sequence of degree distributions is an object of interest which sheds light on the evolving structures. In this article, we use a fluid limit approach to prove a functional law of large numbers for the degree structure in this class, starting from a variety of initial conditions. The method appears robust and applies in particular to `non-tree' evolutions where cycles may develop in the network. A main part of the argument is to analyze an infinite system of coupled ODEs, corresponding to a rate formulation of the law of large numbers limit, in terms of $C_0$-semigroup/dynamical systems methods. These results also resolve a question in Chung, Handjani and Jungreis (2003)., Comment: 25 pages

We consider a service system where agents are invited on-demand. Customers arrive exogenously as a Poisson process and join a customer queue upon arrival if no agent is available. Agents decide to accept or decline invitations after some exponentially distributed random time, and join an agent queue upon invitation acceptance if no customer is waiting. A customer and an agent are matched in the order of customer arrival and agent invitation acceptance under the non-idling condition, and will leave the system simultaneously once matched (service times are irrelevant here). We consider a feedback-based adaptive agent invitation scheme, which controls the number of pending agent invitations, depending on the customer and/or agent queue lengths and their changes. The system process has two components -- `the difference between agent and customer queues' and `the number of pending invitations', and is a countable continuous-time Markov chain. For the case when the customer arrival rate is constant, we establish fluid and diffusion limits, in the asymptotic regime where the customer arrival rate goes to infinity, while the agent response rate is fixed. We prove the process stability and fluid-scale limit interchange, which in particular imply that that both customer and agent waiting times in steady-state vanish in the asymptotic limit. To do this we develop a novel (multi-scale) Lyapunov drift argument; it is required because the process has non-trivial behavior on the state space boundary. When the customer arrival rate is time-varying, we present a fluid limit for the processes in the same asymptotic regime. Simulation experiments are conducted to show good performance of the invitation scheme and accuracy of fluid limit approximations., Comment: Revision. 23 pages, 4 figures

In many call centers, callers may call multiple times. Some of the calls are re-attempts after abandonments (redials), and some are re-attempts after connected calls (reconnects). The combination of redials and reconnects has not been considered when making staffing decisions, while not distinguishing them from the total calls will inevitably lead to under- or overestimation of call volumes, which results in improper and hence costly staffing decisions.Motivated by this, in this paper we study call centers where customers can abandon, and abandoned customers may redial, and when a customer finishes his conversation with an agent, he may reconnect. We use a fluid model to derive first order approximations for the number of customers in the redial and reconnect orbits in the heavy traffic. We show that the fluid limit of such a model is the unique solution to a system of three differential equations. Furthermore, we use the fluid limit to calculate the expected total arrival rate, which is then given as an input to the Erlang A formula for the purpose of calculating the service levels and abandonment probabilities. The performance of such a procedure is validated numerically in the case of both single intervals with constant parameters and multiple intervals with time-dependent parameters. The results demonstrate that this approximation method leads to accurate estimations for the service levels and the abandonment probabilities. We model the customer redial and reconnect behaviors in call centers.We approximate the service levels and abandonment percentages of such a model.A fluid model is proposed, and the corresponding fluid limit is derived.The performance of our approximation is evaluated numerically.

We consider a service system model primarily motivated by the problem of efficient assignment of virtual machines to physical host machines in a network cloud, so that the number of occupied hosts is minimized. There are multiple types of arriving customers, where a customer's mean service time depends on its type. There is an infinite number of servers. Multiple customers can be placed for service into one server, subject to general "packing" constraints. Service times of different customers are independent, even if served simultaneously by the same server. Each new arriving customer is placed for service immediately, either into a server already serving other customers (as long as packing constraints are not violated) or into an idle server. After a service completion, each customer leaves its server and the system. We propose an extremely simple and easily implementable customer placement algorithm, called Greedy-Random (GRAND). It places each arriving customer uniformly at random into either one of the already occupied servers (subject to packing constraints) or one of the so-called zero-servers, which are empty servers designated to be available to new arrivals. One instance of GRAND, called GRAND($aZ$), where $a\ge 0$ is a parameter, is such that the number of zero-servers at any given time $t$ is $aZ(t)$, where $Z(t)$ is the current total number of customers in the system. We prove that GRAND($aZ$) with $a>0$ is asymptotically optimal, as the customer arrival rates grow to infinity and $a\to 0$, in the sense of minimizing the total number of occupied servers in steady state. In addition, we study by simulations various versions of GRAND and observe the dependence of convergence speed and steady-state performance on the number of zero-servers., Revision. 23 pages, 9 figures

We introduce the {\Delta}(i)/GI/1 queue, a new queueing model. In this model, customers from a given population independently sample a time to arrive from some given distribution F. Thus, the arrival times are an ordered statistics, and the inter-arrival times are differences of consecutive ordered statistics. They are served by a single server which provides service according to a general distribution G, with independent service times. The exact model is analytically intractable. Thus, we develop fluid and diffusion limits for the various stochastic processes, and performance metrics. The fluid limit of the queue length is observed to be a reflected process, while the diffusion limit is observed to be a function of a Brownian motion and a Brownian bridge process, and is given by a 'netput' process and a directional derivative of the Skorokhod reflected fluid netput in the direction of a diffusion refinement of the netput process. We also observe what may be interpreted as a transient Little's law. Sample path analysis reveals various operating regimes where the diffusion limit switches between a free diffusion, a reflected diffusion process and the zero process, with possible discontinuities during regime switches. The weak convergence is established in the M1 topology, and it is also shown that this is not possible in the J1 topology., Comment: Accepted, Queueing Systems

We consider the asymptotics of the invariant measure for the process of the empirical spatial distribution of $N$ coupled Markov chains in the limit of a large number of chains. Each chain reflects the stochastic evolution of one particle. The chains are coupled through the dependence of the transition rates on this spatial distribution of particles in the various states. Our model is a caricature for medium access interactions in wireless local area networks. It is also applicable to the study of spread of epidemics in a network. The limiting process satisfies a deterministic ordinary differential equation called the McKean-Vlasov equation. When this differential equation has a unique globally asymptotically stable equilibrium, the spatial distribution asymptotically concentrates on this equilibrium. More generally, its limit points are supported on a subset of the $\omega$-limit sets of the McKean-Vlasov equation. Using a control-theoretic approach, we examine the question of large deviations of the invariant measure from this limit., Comment: 58 pages, reorganised to get quickly to the main results on invariant measure; Stochastic Systems, volume 2, 2012

Performance evaluation of the 802.11 MAC protocol is classically based on the decoupling assumption, which hypothesizes that the backoff processes at different nodes are independent. This decoupling assumption results from mean field convergence and is generally true in transient regime in the asymptotic sense (when the number of wireless nodes tends to infinity), but, contrary to widespread belief, may not necessarily hold in stationary regime. The issue is often related with the existence and uniqueness of a solution to a fixed point equation; however, it was also recently shown that this condition is not sufficient; in contrast, a sufficient condition is a global stability property of the associated ordinary differential equation. In this paper, we give a simple condition that establishes the asymptotic validity of the decoupling assumption for the homogeneous case. We also discuss the heterogeneous and the differentiated service cases and formulate a new ordinary differential equation. We show that the uniqueness of a solution to the associated fixed point equation is not sufficient; we exhibit one case where the fixed point equation has a unique solution but the decoupling assumption is not valid in the asymptotic sense in stationary regime., Comment: 16 pages, 4 figures, accepted for publication in IEEE Transactions on Information Theory

Assume that a stochastic processes can be approximated, when some scale parameter gets large, by a fluid limit (also called "mean field limit", or "hydrodynamic limit"). A common practice, often called the "fixed point approximation" consists in approximating the stationary behaviour of the stochastic process by the stationary points of the fluid limit. It is known that this may be incorrect in general, as the stationary behaviour of the fluid limit may not be described by its stationary points. We show however that, if the stochastic process is reversible, the fixed point approximation is indeed valid. More precisely, we assume that the stochastic process converges to the fluid limit in distribution (hence in probability) at every fixed point in time. This assumption is very weak and holds for a large family of processes, among which many mean field and other interaction models. We show that the reversibility of the stochastic process implies that any limit point of its stationary distribution is concentrated on stationary points of the fluid limit. If the fluid limit has a unique stationary point, it is an approximation of the stationary distribution of the stochastic process., Comment: 7 pages, preprint

We study many-server queues with abandonment in which customers have general service and patience time distributions. The dynamics of the system are modeled using measure- valued processes, to keep track of the residual service and patience times of each customer. Deterministic fluid models are established to provide first-order approximation for this model. The fluid model solution, which is proved to uniquely exists, serves as the fluid limit of the many-server queue, as the number of servers becomes large. Based on the fluid model solution, first-order approximations for various performance quantities are proposed.

In this article, the continuous time random walk on the circle is studied. We derive the corresponding generalized master equation and discuss the effects of topology, especially important when Levy flights are allowed. Then, we work out the fluid limit equation, formulated in terms of the periodic version of the fractional Riemann-Liouville operators, for which we provide explicit expressions. Finally, we compute the propagator in some simple cases. The analysis presented herein should be relevant when investigating anomalous transport phenomena in systems with periodic dimensions., Comment: 14 pages, 1 figure. References added. Published version