On the delay-storage trade-off in content download from coded distributed storage systems

In this paper we study how coding in distributed storage reduces download time, in addition to providing reliability against disk failures. The download time is reduced because when a content file is encoded to add redundancy and distributed across multiple disks, reading only a subset of the disks is sufficient to reconstruct the content. For the same total storage used, coding exploits the diversity in storage better than simple replication, and hence gives faster download. We use a novel fork-join queuing framework to model multiple users requesting the content simultaneously, and derive bounds on the expected download time. Our results demonstrate the fundamental trade-off between the download time and the amount of storage space. This trade-off can be used for design of the amount of redundancy required to meet the delay constraints on content delivery. Index Terms distributed storage, fork-join queues, MDS codes I