Algorithmic Mechanism Design for Data Replication Problems
Minzhe Guo · OhioLink ETD Center (Ohio Library and Information Network) · 2016
Data replication is an important technique in modern storage-capable distributed systems, such as content delivery networks (CDNs), peer-to-peer networks (P2Ps), and mobile networks, for improving system availability, reliability, and fault-tolerance.Most existing studies on data replication problems assume that all participants in the system fully comply with the designed protocols.Nevertheless, in real-world data replication applications, entities, e.g., servers, data providers, or data consumers, can belong to different stakeholders or administrative domains with different preferences and objectives, exhibiting heterogeneous behaviors that may not be consistent with the expected behavior of the designed protocols.This dissertation studies the problems of data replica placement (DRP), a key component in data replication applications, and utilizes algorithmic mechanism design theory to design algorithms for DRP problems in the settings with heterogeneous behavior models.We first study the DRP problem in CDN in a strategic setting where multiple self-interested players with private preferences own data objects for replication.We design quantitative metrics to measure the content delivery cost associated with specific replica placements and investigate the super-modularity and monotonicity of the cost metrics.We then design DRPMECH, an incentive compatible mechanism that approximates a socially efficient solution to the who has been a gentle, patient, far-sighted, and knowledgeable advisor ever since the first day that I came to Cincinnati.Dr. Bhattacharya always provides invaluable guidance and prompt feedback throughout the course of my graduate study.Even during the times when my attention was attracted by other things, he kept encouraging me and helping me to overcome those difficulties.