Data placement is one of the fundamental allocation problems in storage-capable distributed systems. In this problem, the goal is to store copies of data items across cache-capacitated networked servers in order to minimize overall storage and client access costs. It has applications in a variety of settings, such as web caches, peer-to-peer networks, and goods distribution networks. Motivated by these applications, we study the data placement problem under both metric and non-metric access costs and use novel game-theoretic decompositions to develop distributed algorithms for computing or approximating optimal solutions. We first show that the data placement problem under metric and non-metric access costs is inapproximable within constant and logarithmic factors, respectively. We then provide game-theoretic decompositions of the objective functions and leverage them to design polynomial-time distributed algorithms that achieve approximate solutions with theoretical performance guarantees. The proposed algorithms not only provide strong performance guarantees but also enable the system to operate in a fully distributed (and even online) manner, thereby reducing computational load and improving robustness to network failures.
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 Electrical and Computer Engineering at Princeton University and WINLAB. He received his Ph.D. in Electrical and Computer Engineering from UIUC in 2015. His research focuses on the analysis of complex decision-making systems using tools from control theory, game theory, optimization, and learning. He was the recipient of the NSF CAREER Award (2020), the U.S. Air Force Young Investigator Award (2023), the SIAM Journal on Control and Optimization Best Paper Award (2025), and several other teaching and research awards.
