Delay, Memory, and Messaging Tradeoffs in Distributed Service Systems

We consider the following distributed service model: jobs with independent processing times of unit mean arrive as a Poisson process of rate \lambda N, with 0<\lambda<1 fixed, and are immediately dispatched to one of several queues associated with N identical servers. We assume that the dispatching decisions are made by a central dispatcher endowed with a  finite memory, and with the ability to exchange messages with the servers.

We study the fundamental resource requirements (memory bits and message exchange rate), in order to drive the expected steady-state queueing delay of a typical job to zero, as increases. We propose a certain policy and establish that it drives the delay to zero when either (i) the message rate grows superlinearly with N, or (ii) the memory grows superlogarithmically with N. Moreover, we show that any policy that has a certain symmetry property, and for which neither condition (i) or (ii) holds, results in an expected queueing delay which is bounded away from zero.