Consistency and Complexity Tradeoffs for Highly-Available Multi-Cloud Store

Cloud-based storage services have established themselves as a
paradigm of choice for supporting bulk storage needs of modern
networked services and applications. Although individual storage
service providers can be trusted to do their best to reliably store
the user data, exclusive reliance on any single provider or storage
service leaves the users inherently at risk of being locked out of
their data due to outages, connectivity problems, and unforeseen
alterations of the service contracts. An emerging multi-cloud
storage paradigm addresses these concerns by replicating data across
multiple cloud storage services, potentially operated by distinct
providers. In this paper, we study the impact of the storage
interfaces and consistency semantics exposed by individual clouds on
the complexity of the reliable multi-cloud storage
implementation. Our results establish several inherent space and
time tradeoffs associated with emulating reliable objects over a
collection of unreliable storage services with varied interfaces and
consistency guarantees.