On the Delay-Storage Trade-Off in Content Download from Coded Distributed Storage Systems

By Gauri Joshi, Yanpei Liu, Emina Soljanin. 2013

198 citations recorded by the source corpus.

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 with redundancy and distributed across multiple disks, reading only a subset of the disks is sufficient for content reconstruction. 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 queueing 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.

Subfields: Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Speeding Up Distributed Machine Learning Using Codes (2015, background): “[39] show that scheduling redundant requests to an increased number of storage nodes can improve the latency performance, and characterize the resulting storage-latency tradeoff.”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, methodology): “We provide a technique (building on [2]–[5]) that introduces redundancy in the computation by designing a new error correction mechanism that allows the size of the individual dot products computed at each processing node to be shorter than the length of the input.”
Efficient task replication for fast response times in parallel computation (2014, unknown): “SIGMETRICS 14, June 16 20, 2014, Austin, Texas, USA.”
Queues with Redundancy: Latency-Cost Analysis (2015, background): “Only bounds are known for general k and n [3, 5].”
Analyzing the download time of availability codes (2015, methodology): “Our work is inspired by a series of recent studies [3], [4], [5], [6], [7], which have analyzed codes (mainly, MDS”
Using Straggler Replication to Reduce Latency in Large-scale Parallel Computing (2015, background): “Note that the use of redundancy to reduce latency has also attracted attention in other contexts such as cloud storage and networking [8, 10].”
Coded convolution for parallel and distributed computing within a deadline (2017, unknown): “The use of replication [6], [7], [8] is a natural strategy for dealing with stragglers in distributed systems since the computation only requires a subset of the processors to ﬁnish.”