TITLE: Delay, memory, and messaging tradeoffs in distributed service systems

ABSTRACT:

Distributed service systems such as data-centers and multi-core processors have enabled the exponential growth of the network infrastructure that supports the Internet. From the point of view of an administrator of such systems, the objective is to provide the best possible service to the customers (fast response times), using the least possible amount of control overhead.

These systems, and many more, can be analyzed using the following abstract model: a single stream of jobs 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 with unit processing rate. 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.

In this setting, we study the fundamental resource requirements (in terms of memory bits and message exchange rate), in order to drive the expected steady-state queueing delay of a typical job to zero, as N 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.

BIO: Martin Zubeldia is a PhD candidate in the Laboratory for Information and Decision Systems at MIT, advised by professors David Gamarnik and John N. Tsitsiklis. Before joining MIT, he obtained a B.S. and a M.Sc. in Electrical Engineering from Universidad ORT Uruguay, in 2012 and 2014 respectively. His primary research interests lie broadly in the fields of applied probability and queueing theory, with a special emphasis in large-scale decision systems, and the tradeoffs between information and performance in those systems.