The Asymptotics of Selecting the Shortest of Two, Improved

This result was generalized to natural queueing models independently in [6] and [2, 3]. Suppose that tasks arrive at a bank of n First In First Out processors as a Poisson process of rate *n, where * ! 1; tasks require an exponentially distributed amount of service with mean 1. If each task queues at a random processor, then in the stationary distribution the probability that a server has at least k tasks is simply *k. If instead each task chooses two processors at random and queues at the shorter, then in the fluid limit process representing the limiting behavior as n grows, the probability that a server has at least k tasks converges to * dk\Gamma 1 d\Gamma 1. That is, the tails of the processor queue lengths decrease doubly exponentially, rather than exponentially, when d? 1. The effect is clear in simulations even for relatively small values of n. In this paper, we consider a variation based on the work by V"ocking [5]. In his basic model, n bins are split into d groups of size n=d. We think of these groups as being laid out linearly, with the first group (bins 1 to n=d) being the leftmost, and so on. A ball is placed by choos\Lambda Harvard University, Computer Science Department. 29 Oxford St., Cambridge, MA 02138. email:michaelm@eecs.harvard.edu