We consider the following natural model: customers arrive as a Poisson stream of rate $\lambda n$, $\lambda < 1$, at a collection of $n$ servers. Each customer chooses some constant $d$ servers independently and uniformly at random from the $n$ servers, and waits for service at the one with the fewest customers. Customers are served according to the first-in first-out (FIFO) protocol, and the service time for a customer is exponentially distributed with mean 1. We call this problem the {\em supermarket model}. We wish to know how the system behaves, and in particular we are interested the effect the parameter $d$ has on expected time a customer spends in the system in equilibrium.
Our approach uses a limiting, deterministic model representing the behavior as $n \rightarrow \infty$ to approximate the behavior of finite systems. The analysis of the deterministic model is interesting in its own right. Along with a theoretical justification of this approach, we provide simulations that demonstrate the method accurately predicts system behavior even for relatively small systems.
Our analysis provides surprising implications: having $d = 2$ choices leads to exponential improvements in the expected time a customer spends in the system over $d = 1$, whereas having $d=3$ choices is only a constant factor better than $d=2$. We discuss the possible implications for system design.
Originally appeared in the Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, pp. 213-222, 1996.