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