Dia 2 de agosto (quinta), 10h, na sala H324-B (bloco H do CT), receberemos o
prof. Sem Borst (Eindhoven University of Technology & Nokia Bell Labs)

O Sem é um consagrado pesquisador na área de
modelagem matemática de sistemas e pesquisa operacional, co-autor de
mais de 25 patentes e 170 artigos científicos, com passagem pela
indústria e academia, tendo recebido o ACM SIGMETRICS Achievement
Award em 2017 (em
https://www.sigmetrics.org/achievementaward-2017.shtml).

—
Palestrante: Sem Borst, Full Professor and Senior Researcher,
Eindhoven University of Technology & Nokia Bell Labs

Título:
Scalable Load Balancing in Networked Systems

Dia/horário/local:
2 de agosto (quinta), 10h, sala H324-B

Resumo:
We will discuss scalable load balancing algorithms, which provide
favorable delay performance in large-scale systems, and yet only
require minimal implementation overhead. Through the initial stages of
the talk we focus on a basic setup – commonly referred to as the
supermarket model – with a single dispatcher and N identical parallel
servers. A popular class of load balancing algorithms are so-called
JSQ(d) policies, where an incoming task is assigned to a server with
the shortest queue among d servers selected uniformly at random. As
the name reflects, this class includes the celebrated
Join-the-Shortest-Queue (JSQ) policy as a special case (d = N), which
has strong stochastic optimality properties.

In order to explore the fundamental trade-off between delay
performance and implementation overhead, we consider an asymptotic
regime where the total arrival rate and number of servers N grow large
in proportion and the diversity parameter d(N) depends on N. We show
that the fluid limit and the diffusion limit correspond to those for
the ordinary JSQ policy when d(N) tends to infinity and d(N) /
(sqrt(N) log(N)) tends to infinity, respectively, as the number of
servers N grows large. Thus, the optimality of the JSQ policy can be
retained at fluid level and diffusion level while reducing the amount
of communication overhead by nearly a factor N and sqrt(N) / log(N),
respectively. In addition, we analyze load balancing mechanisms which
leverage memory at the dispatcher in order to reduce the amount of
communication overhead further while maintaining low delay.

Bio resumida:
Sem Borst has been a professor in Stochastic Operations Research at
Eindhoven University of Technology since 1998. He also has a part-time
position with Nokia Bell Labs in Murray Hill, NJ, USA. His main
research areas are performance evaluation and resource allocation for
stochastic systems, in particular computer-communication networks. He
has published over 170 refereed papers and holds 28 patents in various
areas. Sem serves or has served on the editorial boards of several
journals, such as ACM Transactions on Modeling and Performance
Evaluation of Computing Systems, IEEE/ACM Transactions on Networking,
Mathematical Methods of Operations Research, Performance Evaluation,
Queueing Systems and Wireless Networks. He was recipient of the
best-paper awards at ACM SIGMETRICS/Performance 1992 and Infocom 2003,
the 1994 Gijs de Leve Prize, the 2001 Yosef Levy Prize, the 2005 Van
Dantzig Prize, and the 2017 ACM SIGMETRICS Achievement Award.