Provable Storage Medium for Data Storage Outsourcing

In remote storage services, delays in the time to retrieve data can cause economic losses to the data owners. In this paper, we address the problem of properly establishing specific clauses in the service level agreement (SLA), intended to guarantee a short and predictable retrieval time. Based on the rationale that the retrieval time mainly depends on the storage media used at the server side, we introduce the concept of Provable Storage Medium (PSM), to denote the ability of a user to efficiently verify that the provider is complying to this aspect of the SLA. We propose PSM as an extension of Provable Data Possession (PDP): embedding challenge-response PDP schemes with measurements of the response time, both properties can be enforced without any need for the user to locally store nor download her data. We describe a realistic implementation of PSM in a scenario where data should be stored both in RAM and HDD. A thorough analysis shows that, even for relatively small challenges, the total time to compute and deliver the response is sensibly affected by the remarkable difference in the access time of the two supports. An extensive simulation campaign confirms the quality and viability of our proposal.