On the power of two choices: Balls and bins in continuous time

Suppose that there are n bins, and balls arrive in a Poisson process at rate .n, where .>0 is a constant. Upon arrival, each ball chooses a fixed number d of random bins, and is placed into one with least load. Balls have independent exponential lifetimes with unit mean. We show that the system converges rapidly to its equilibrium distribution; and when d.2, there is an integer-valued function md(n)=ln.ln.n/ln.d+O(1) such that, in the equilibrium distribution, the maximum load of a bin is concentrated on the two values md(n) and md(n).1, with probability tending to 1, as n... We show also that the maximum load usually does not vary by more than a constant amount from ln.ln.n/ln.d, even over quite long periods of time.