Search

We set out a general procedure which allows the approximation of certain Markov chains by the solutions of differential equations. The chains considered have some components which oscillate rapidly and randomly, while others are close to deterministic. The limiting dynamics are obtained by averaging the drift of the latter with respect to a local equilibrium distribution of the former. Some general estimates are proved under a uniform mixing condition on the fast variable which give explicit error probabilities for the fluid approximation. Mitzenmacher, Prabhakar and Shah [In Proc. 43rd Ann. Symp. Found. Comp. Sci. (2002) 799-808, IEEE] introduced a variant with memory of the "join the shortest queue" or "supermarket" model, and obtained a limit picture for the case of a stable system in which the number of queues and the total arrival rate are large. In this limit, the empirical distribution of queue sizes satisfies a differential equation, while the memory of the system oscillates rapidly and randomly. We illustrate our general fluid limit estimate by giving a proof of this limit picture., Published in at http://dx.doi.org/10.1214/12-AAP861 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We prove three strong approximation theorems for the `supermarket' or `join the shortest queue' model -- a law of large numbers, a jump process approximation and a central limit theorem. The estimates are carried through rather explicitly. This allows us to estimate each of the infinitely many components of the process in its own scale and to exhibit a cut-off in the set of active components which grows slowly with the number of servers., 27 pages

We consider the stability of a network serving a patchwork of overlapping regions where customers from a local region are assigned to a collection of local servers.These customers join the queue of the local server with the shortest queue of waiting customers.We then describe how the backlog in the network overloads.We do this in the simple case of two servers each of which receives a dedicated stream of customers in addition to customers from a stream of smart customers who join the shorter queue. There are three distinct ways the backlog can overload. If one server is very fast, then that server takes all the smart customers along with its dedicated customers and keeps its queue small while the dedicated customers at the other server cause the overload.We call this the unpooled case. If the proportion of smart customers is large, then the two servers overload in tandem.We call this the strongly pooled case. Finally, there is the weakly pooled case where both queues overload but in different proportions. The fact that strong pooling can be attained based on a local protocol for overlapping regions may have engineering significance. In addition, this paper extends the methodology developed in McDonald (to appear The Annals of Applied Probability) to cover periodicities. The emphasis here is on sharp asymptotics, not rough asymptotics as in large deviation theory. Moreover, the limiting distributions are for the unscaled process, not for the fluid limit as in large deviation theory. In the strongly pooled case, for instance, we give the limiting distribution of the difference between the two queues as the backlog grows.We also give the exact asymptotics of the mean time until overload.