Computation and Storage in the Cloud

Appendix B

Proofs of Theorems, Lemmas and Corollaries

Theorem 5.1

Given a linear DDG with data sets {d₁, d₂, …, d_n}, the length of P_min<d_s, d_e> of its CTT is the minimum cost rate for storing the data sets in the DDG, and the corresponding storage strategy is to store the data sets that P_min<d_s, d_e> traverses.

Proof of Theorem 5.1: First, there is a one-to-one mapping between the storage strategies of the DDG and the paths from d_s to d_e in the CTT. Given any storage strategy of the DDG, we can find an order of these stored data sets, since the DDG is linear. Then, we can find the exact path in the CTT that has traversed all these stored data sets. Similarly, given any path from d_s to d_e in the CTT, we can find the data sets it has traversed, ...