An emerging multi-cloud storage paradigm suggests 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.