**Speaker**:

Professor John Tsitsiklis (MIT)

**TITLE:**

Delay, memory, and messaging tradeoffs in a distributed service
system

**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 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.

Joint work with D. Gamarnik and M. Zubeldia.

**Bio:**

John N. Tsitsiklis received the B.S.
degree in mathematics and the B.S., M.S., and Ph.D. degrees in electrical
engineering from the Massachusetts Institute of Technology (MIT), Cambridge,
MA, USA, in 1980, 1980, 1981, and 1984, respectively. His research interests
are in systems, optimization, communications, control, and operations research.
He has coauthored four books and several journal papers in these areas. He is
currently a Clarence J. Lebel Professor with the
Department of Electrical Engineering and Computer Science, MIT, where he serves
as the director of the Laboratory for Information and Decision Systems. He is a
member of the National Academy of Engineering and holds an honorary doctorate
from the UniversitŽ catholique
de Louvain, Louvain-la-Neuve, Belgium. Among other
distinctions, he is a recipient of the ACM SIGMETRICS Achievement Award (2016)
and the IEEE Control Systems Award (2018).