SCS Faculty Candidate
- Newell-Simon Hall
- ARPAN MUKHOPADHYAY
- Postdoctoral Researcher
- School of Computer and Communication Sciences
- École polytechnique fédérale de Lausanne (EPFL).
Efficient Algorithm Design and Analysis for Large Systems: A Mean Field Approach
Key challenges in large-scale systems such as cloud data centers, server farms, content delivery networks, and social networks include efficient allocation of resources to user requests and analyzing the dynamics of information diffusion processes. Addressing these problems often involves modeling the dynamics of the system as a Markov process. However, the complex interaction among the entities of the network makes an exact analysis of this Markov process prohibitively difficult. Mean field theory has recently proven to be effective in approximating such Markov processes for large-scale systems.
In this talk, we shall discuss our work in designing asymptotically optimal algorithms for large scale service-systems using mean field techniques. To begin with, we consider content delivery networks supporting video-on-demand systems such as Netflix and YouTube. The problem is to minimize the drop rate of requests by jointly optimizing over the set of content replication policies and request matching policies. While the joint optimization problem is NP-hard for finite systems, using mean field techniques we show that in the large system limit a simple greedy scheme achieves optimality. We shall then discuss two other important applications of mean field techniques: (I) analyzing the performance simple randomized load balancing schemes for large scale cloud computing platforms and (II) analyzing the mean time to reach consensus in large social networks. Finally, we conclude with long term research directions.
Arpan Mukhopadhyay is a postdoctoral researcher at the School of Computer and Communication Sciences, EPFL. Prior to joining EPFL, he spent one year as a postdoctoral researcher at INRIA, Paris, France. He obtained his Ph.D. in 2016 from the ECE Department of the University of Waterloo, Canada. His research interest lies in the application of probability theory, stochastic processes, and optimization to designing efficient algorithms for large network systems. Recently, he has been working on problems in energy networks with the goal of optimizing electrical grids’ operations under the uncertainties of renewable generation. His works received best paper awards in IFIP Performance 2015 and ITC 2015.
Faculty Host: Mor Harchol-Balter