Estamos retomando o Ciclo de Seminários PESC em grande estilo.

Prof. Sem Borst (Eindhovens University of Technology & Nokia Bell Lab): consagrado pesquisador na área de modelagem matemática de sistemas computacionais, co-autor de mais de 25 patentes e 170 artigos científicos, com passagem pela indústria e academia (detalhes clicando aqui).

Dia 2 de agosto (quinta), 10h, título "Scalable Load Balancing in Networked Systems".

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.

A key facet of the supermarket model is that any task can be handled equally efficiently by any server, which provides analytical tractability but does not cover situations where the processing speeds of a specific task at the various servers may be different. These scenarios may arise due to data locality, task-server affinity relations, or broader compatibility constraints. In order to capture such heterogeneity features, we broaden the attention to network scenarios where the various servers are interconnected by some underlying graph topology G_N. Tasks arrive with rate lambda at each of the N servers, and each task is assigned to the server with the shortest queue among the one where it appears and its neighbors in the graph G_N. We establish conditions - in terms of the average degree and structure of the graph G_N - for the fluid-scaled and diffusion-scaled occupancy processes to be equivalent to those for the case of a clique. The results demonstrate that the optimality of a clique can be asymptotically achieved with far fewer connections, provided the graph topology G_N is suitably random.

Note: Based on joint work with Mark van der Boor, Johan van Leeuwaarden, Debankur Mukherjee and Phil Whiting.

Programe-se, participe e ajude na divulgação!