  In this paper we study how coding in distributed storage reduces expected
download time, in addition to providing reliability against disk failures. The
expected 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 system model and results are a novel
generalization of the fork-join system that is studied in queueing theory
literature. Our results demonstrate the fundamental trade-off between the
expected 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.
