Distributed storage solutions have become widespread due to their ability to store large amounts of data reliably across a network of unreliable nodes, by employing repair mechanisms to prevent data loss. Conventional systems rely on static designs with a central control entity to oversee and control the repair process. Given the large costs for maintaining and cooling large data centers, our work proposes and studies the feasibility of a fully decentralized systems that can store data even on unreliable and, sometimes, unavailable mobile devices. This imposes new challenges on the design as the number of available nodes varies greatly over time and keeping track of the system's state becomes unfeasible. As a consequence, conventional erasure correction approaches are ill-suited for maintaining data integrity. In this highly dynamic context, random linear network coding (RLNC) provides an interesting solution. Our goal is to characterize RLNC's guaranteed data integrity region in terms of the total number of storage devices that need to be available and stored data per device. We compare our fully distributed RLNC approach to centralized (genie aided) and fully decentralized replication and Reed-Solomon mechanisms. Our results use traces from a BitTorrent client for Android devices to show that RLNC outperforms the next best scheme (fully centralized Reed-Solomon) not only by having a much lower probability of data loss, but by reducing storage requirements by up to 50% and reconstruction traffic by up to 40%. Gains over decentralized schemes are even larger.