Abstract: We consider the classical supermarket model: jobs arrive as a Poisson process of rate of $\lambda N$, with $0 < \lambda < 1$, and are to be routed to one of $N$ identical servers with unit mean, exponentially distributed processing times. We review a variety of policies and architectures that have been considered in the literature, and which differ in terms of the direction and number of messages that are exchanged, and the memory that they employ; for example, the ''power-of-$d$-choices'' or pull-based policies. In order to compare policies of this kind, we focus on the resources (memory and messaging) that they use, and on whether the expected delay of a typical vanishes as $N$ increases.
We show that if (i) the message rate increases superlinearly, or (ii) the memory size increases superlogarithmically, as a function of $N$, then there exists a policy that drives the delay to zero, and we provide a detailed analysis using fluid models. On the other hand, if neither condition (i) or (ii) holds, then any policy within a broad class of symmetric policies cannot yield vanishing delay.

Joint work with D. Gamarnik and M. Zubeldia.