Data placement is one of the fundamental allocation problems in storage-capable distributed systems, such as web caches and peer-to-peer networks. Motivated by such applications, we consider the non-metric data placement problem and develop distributed algorithms for computing or approximating its optimal solutions. In this problem, the goal is to store copies of the data points among cache-capacitated servers to minimize overall data storage and clients’ access costs. We first show that the non-metric data placement problem is inapproximable up to a logarithmic factor. We then provide a game-theoretic decomposition of the objective function and show that natural Glauber dynamics will converge to an optimal global solution with polynomial mixing time for a certain range of noise parameters. Moreover, we provide another auction-based distributed algorithm, which allows us to approximate the optimal solution with a theoretical performance guarantee. The proposed algorithms not only provide good performance guarantees but also will enable the system to operate in a distributed manner, hence reducing the computational load and improving the robustness to failures.

Papers:

https://dl.acm.org/doi/10.1145/3589334.3645654

Rasoul Etesami is an Associate Professor in the Department of Industrial and Systems Engineering at the University of Illinois Urbana-Champaign (UIUC), where he is also affiliated with the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory. From 2016 to 2017, he was a Postdoctoral Research Fellow in the Department of Electrical Engineering at Princeton University. He received his Ph.D. in Electrical and Computer Engineering from UIUC in 2016. His research interests include the analysis of complex social, communication, and decision-making systems using tools from control and game theory, optimization, and learning theory. He was the recipient of the Best CSL Ph.D. Thesis Award at UIUC, Springer Outstanding Ph.D. Thesis Award, NSF CAREER Award, Air Force Young Investigator Award, and James Franklin Sharp Outstanding Teaching Award.

For more information about the ESD Seminar, please email esd_invite@sutd.edu.sg