Appendix B

Proofs of Theorems, Lemmas and Corollaries

Theorem 5.1

Given a linear DDG with data sets {d1, d2, , dn}, the length of Pmin<ds, de> 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 Pmin<ds, de> 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 ds to de 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 ds to de in the CTT, we can find the data sets it has traversed, ...

Get Computation and Storage in the Cloud now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.