CESG Fishbowl (Room 333 WEB)
John N. Tsitsiklis
Dept. of Electrical Engineering and Computer Science
We consider a multiserver system that exhibits a limited degree of flexibility. There are n independent arrival streams and n associated queues. A fraction p of the total available service rate is deployed as a flexible manner, in the form of a server with rate np that can serve any type of arriving tasks, while the remaining fraction 1−p is allocated to n local servers each associated with one of the n queues. It is known that if the pooled resource always chooses to serve a job from the longest queue, and under the usual Poisson/exponential assumptions) the resulting queueing delay scales (in the limit of large n) as the logarithm of 1/(1-rho), where rho stands for the utilization level of the system; this is qualitatively better than the 1/(1-rho) scaling obtained for the case of p=0 and n indepedent queues.
We argue that the same performance can be obtained by a “push” architecture under which arriving tasks are diverted to the flexible server whenever the corresponding local queue exceeds a suitably chosen threshold. Furthermore, the analysis carries over to a much broader interarrival and service time distributions.
We also consider an alternative model that exhbits a limited degree of flexibility, whereby each server is allowed to serve only a relatively small number of arrival streams. We argue that with a judicious choice of interconnection topology and scheduling policy, a large capacity region and vanishing delays are simultaneously achievable.
(Joint work with Kuang Xu.)
John N. Tsitsiklis received the B.S. degree in Mathematics (1980), and the B.S. (1980), M.S. (1981) and Ph.D. (1984) degrees in Electrical Engineering, all from M.I.T., where he is currently a Clarence J Lebel Professor of Electrical Engineering. He has served as a co-director of the MIT Operations Research Center (2002-5), and a co-associate director of the Laboratory of Information and Decision Systems. As of 2013, he is serving as the Chair of the Council of the Harokopio University, in Greece.
His research interests are in the fields of systems, optimization, communications, control, and operations research. He has coauthored four books and several journal papers in these areas. He is a coauthor of Parallel and Distributed Computation: Numerical Methods (1989, with D. Bertsekas), Neuro-Dynamic Programming (1996, with D. Bertsekas), Introduction to Linear Optimization (1997, with D. Bertsimas), and Introduction to Probability (2002, with D. Bertsekas).
He has been a recipient of an IBM Faculty Development Award (1983), an NSF Presidential Young Investigator Award (1986), an Outstanding Paper Award by the IEEE Control Systems Society (1986), the M.I.T. Edgerton Faculty Achievement Award (1989), the Bodossaki Foundation Prize (1995), and a co-recipient of two INFORMS Computing Society prizes (1997, 2012), and a Sigmetrics Best paper award (2013). He is a Fellow of the IEEE (1999) and of INFORMS (2007). In 2007, he was elected to the National Academy of Engineering. In 2008, he was conferred the title of Doctor honoris causa from the Universite catholique de Louvain (Belgium).