TITLE: Scalable Task Allocation in Distributed Systems

ABSTRACT:

A fundamental challenge in large-scale service systems is to strike a proper balance in terms of the performance-complexity tradeoff. While optimal performance often entails a highly complex system design, minimizing complexity tends to significantly worsen the performance. In the context of task assignment in large-scale service systems, the above can be perceived through the prohibitively high communication burden of the delay-optimal Join-the-Shortest Queue policy and much worse delay performance of the random assignment policy, which has zero communication overhead.

In this talk, we first show that asymptotically optimal performance can be achieved on fluid and diffusion scale while drastically reducing the complexity of the optimal policy, as the number of servers becomes large. Considering further the aspect of energy consumption, we continue to examine the performance-complexity-energy tradeoff, and provide a token-based joint auto-scaling and task assignment algorithm that provably achieves asymptotic optimality in all three aspects. Next, we discuss novel stochastic comparison arguments and non-classical stochastic process limit theorems which form the basis for obtaining the above results. The problem is fundamentally more complicated when the servers interact through some graph topology. We present our recent results in this direction that examine the impact of the network topology on the performance of the system. We will end the talk with a brief discussion of several new research directions that emerge from the above line of works.

BIO: Debankur Mukherjee is currently a doctoral candidate at Eindhoven University of Technology, The Netherlands, working under the supervision of Professor Sem Borst and Professor Johan van Leeuwaarden. Before joining the doctoral program, Mukherjee obtained a masters degree from the Indian Statistical Institute, Kolkata, with mathematical statistics and probability specialization.

Mukherjee’s primary research spans the areas of probability theory and stochastic networks, at the interface of stochastic theory and computer science, with applications in queueing theory, stochastic modeling, performance analysis, random graphs, and randomized algorithms. His major contributions towards the field of load balancing and scheduling in large-scale stochastic networks include developing novel coupling techniques and establishing non-classical stochastic process limit theorems to study the delay-communication-energy trade-off in large networks viz. data centers and cloud networks. He also introduced a stochastic comparison framework to study mean-field limits of processes on networks and examined the impact of the network topology on the performance of load balancing schemes in large-scale systems.