Although reliable distributed and cloud storage systems have attracted significant attention over the past decade, until recently, relatively little has been known about fundamental space tradeoffs involved in their implementations. In this talk, I will review the results of our recent study where we explored these tradeoffs in the context of two most commonly used implementation techniques: replication and error-correction coding. Our results reveal that concurrent writing along with failures and asynchrony pose formidable obstacles for realizing space-efficient storage systems using either technique, even for the simplest read/write storage services. The talk will be self-contained and accessible for general CS audience though some familiarity with distributed systems will be an advantage. Based on the joint work with Yuval Cassuto, Idit Keidar, and Sasha Spiegelman, Technion, published in PODC'16 and PODC'17.