Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


20977.pdf (2.36 MB)

ETD Abstract Container

Abstract Header

Algorithmic Mechanism Design for Data Replication Problems

Guo, Minzhe
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470757536

Abstract Details

2016, PhD, University of Cincinnati, Engineering and Applied Science: Computer Science and Engineering.
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 problem. A detailed set of experiments validates the properties of DRPMECH and shows that it outperforms a state-of-the-art game-theoretical algorithm. Next, we study the DRP problem in peer-assisted content delivery networks (PCDNs) with self-interested seeders. Recently, PCDNs have been proposed for simultaneously obtaining the scalability advantage of P2Ps and the reliability and manageability advantages of CDNs. However, the benefits of peer assistance can be severely affected by the self-interested nature of peers, who in general wish to download more and upload less, unless otherwise motivated. We present DPRP-IC, a decentralized algorithm for DRP in PCDNs, which considers peer contributions and incentives self-interested seeders. We investigate the incentive compatibility of the algorithm and design experiments to evaluate its performance. Results suggest that replica placement algorithms that consider peer contributions have better performance in PCDN; in addition, our approach incentivizes the contribution of self-interested seeders and further improves the performance of replica placement in PCDN. Finally, we study the impact of malicious behaviors on the mechanism design. We identify two types of adversaries in the system, design quantitative metrics to measure the magnitude of malice, and experimentally evaluate the impact of malicious behaviors on the DPRP-IC algorithm. We then integrate the probability of malice of each agent into mechanism design and extend DPRP-IC to a security aware solution, DPRP-IC-SA, which is more resilient to malicious attacks, as demonstrated with a detailed set of experiments.
Prabir Bhattacharya, Ph.D. (Committee Chair)
Ki Jung Lee, Ph.D. (Committee Member)
Dharma Agrawal, D.Sc. (Committee Member)
Raj Bhatnagar, Ph.D. (Committee Member)
John Franco, Ph.D. (Committee Member)
149 p.
Computer Science
algorithmic mechanism design; content delivery; data replica placement; malicious; peer-assisted; self-interested

Recommended Citations

Citations

  • Guo, M. (2016). Algorithmic Mechanism Design for Data Replication Problems [Doctoral dissertation, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470757536

    APA Style (7th edition)

  • Guo, Minzhe. Algorithmic Mechanism Design for Data Replication Problems. 2016. University of Cincinnati, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470757536.

    MLA Style (8th edition)

  • Guo, Minzhe. "Algorithmic Mechanism Design for Data Replication Problems." Doctoral dissertation, University of Cincinnati, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470757536

    Chicago Manual of Style (17th edition)

ucin1470757536
396
© 2016, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.