2020 Markov Lecture

November 9, 2020 11:30 a.m. – 1:00 p.m. (Eastern Time)



Sem Borst

Markov Lecturer


Eindhoven University of Technology, The Netherlands


Slides (Markov lecture)

Neil Walton

Discussant


University of Manchester, UK


Slides (Discussion)

Zoom link:
YouTube Live stream:


Load Balancing in Networked Systems: Scalable Algorithms and Resource Pooling Issues

Abstract

Load balancing algorithms play a crucial role in distributing service requests in large-scale parallel-resource systems such as data centers and cloud networks. Due to the massive size of these systems, implementation complexity of load balancing algorithms has emerged as a critical concern besides conventional performance metrics such as delay. In the first part of the talk we explore fundamental trade-offs between these two criteria in the baseline scenario of the celebrated supermarket model. We establish asymptotic universality properties for a broad class of randomized algorithms, and discuss some related resource pooling perspectives.

In the second part of the talk we move beyond the supermarket model, and turn to network settings and multi-class systems with compatibility constraints. These scenarios may arise due to heterogeneity issues and network topology and locality constraints which are increasingly common in data centers and cloud environments. We identify conditions in terms of the underlying compatibility graph in order for similar universality properties to hold in a many-server scenario, and leverage product-form distributions for related redundancy models to demonstrate resource pooling a heavy-traffic regime. Strikingly, across a wise range of scenarios, the performance of a fully flexible system can be matched even with quite stringent compatibility constraints.

Note: Based on joint work with Ellen Cardinaels, Johan van Leeuwaarden, Debankur Mukherjee (Georgia Tech) and Phil Whiting (Macquarie)

Bio

Sem Borst has been a Full Professor in Stochastic Operations Research in the Department of Mathematics & Computer Science at Eindhoven University of Technology (TU/e) since 1998. He also had a (part-time) position in the Mathematics of Systems research department at Bell Laboratories in Murray Hill, USA, from 1995 to 2019, and was a Senior Researcher at the Center for Mathematics & Computer Science (CWI) in Amsterdam from 1998 to 2006. During the fall of 1994, he was a visiting scholar at the Statistical Laboratory of the University of Cambridge, England. His main research interests are in the area of performance evaluation and resource allocation algorithms for large-scale stochastic networks, in particular computer-communication systems.

Sem was (co-)recipient of the best-paper awards at SIGMETRICS/Performance 1992 and IEEE Infocom 2003, the 2001 Yosef Levy Prize, the 2005 Van Dantzig Prize, and the 2017 ACM SIGMETRICS Achievement Award. He serves or has served on the editorial boards of several journals, such as ACM Transactions on Modeling and Performance of Computing Systems, IEEE/ACM Transactions on Networking, Operations Research, Queueing Systems and Stochastic Models, and has been a program committee member of numerous conferences.