Paper Info
Title
Timely Coded Computing
Abstract
In modern distributed computing systems, unpredictable and unreliable infrastructures result in high variability of computing resources. Meanwhile, there is significantly increasing demand for timely and event-driven services with deadline constraints. Motivated by measurements over Amazon EC2 clusters, we consider a two-state Markov model for variability of computing speed in cloud networks. In this model, each worker can be either in a good state or a bad state in terms of the computation speed, and the transition between these states is modeled as a Markov chain which is unknown to the scheduler. We then consider a Coded Computing framework, in which the data is possibly encoded and stored at the worker nodes in order to provide robustness against nodes that may be in a bad state. Our goal is to design the optimal computation-load allocation strategy that maximizes the timely computation throughput (i.e, the average number of computation tasks accomplished before their deadline). Our main result is the development of a dynamic computation strategy called Estimate-and-Allocate (EA) strategy, which achieves the optimal timely computation throughput. Compared with the static allocation strategy, EA improves the timely computation throughput by 1.44x similar to 4.6x in experiments over Amazon EC2 clusters.
Year
DOI
Venue
2019
10.1109/ISIT.2019.8849235
2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT)
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Chien-Sheng Yang1122.24
Ramtin Pedarsani217129.35
Amir Salman Avestimehr31880157.39