2016/04/09 by Xiaoqi Ren, Palma London, Ren, Xiaoqi +5 · 1 citation
Computer Science · #Cryptography and Data Security #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1604.02533
openalex publication_date 2016/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies two design tasks faced by a geo-distributed cloud data market: which data to purchase (data purchasing) and where to place/replicate the data for delivery (data placement). We show that the joint problem of data purchasing and data placement within a cloud data market can be viewed as a facility location problem, and is thus NP-hard. However, we give a provably optimal algorithm for the case of a data market made up of a single data center, and then generalize the structure from the single data center setting in order to develop a near-optimal, polynomial-time algorithm for a geo-distributed data market. The resulting design, Datum, decomposes the joint purchasing and placement problem into two subproblems, one for data purchasing and one for data placement, using a transformation of the underlying bandwidth costs. We show, via a case study, that Datum is near-optimal (within 1.6%) in practical settings.