## ISL Colloquium: Delay, memory, and messaging tradeoffs in a distributed service system

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 outline an analysis using fluid models. On the other hand, if neither condition (i) or (ii) holds, then no policy within a broad class of symmetric policies can yield vanishing delay.