TY - GEN
T1 - Efficient replication of queued tasks for latency reduction in cloud systems
AU - Joshi, Gauri
AU - Soljanin, Emina
AU - Wornell, Gregory
N1 - Funding Information:
This work was supported in part by NSF under Grant No. CCF-1319828, AFOSR under Grant No. FA9550-11-1-0183, and a Schlumberger Faculty for the Future Fellowship.
Publisher Copyright:
© 2015 IEEE.
PY - 2016/4/4
Y1 - 2016/4/4
N2 - In cloud computing systems, assigning a job to multiple servers and waiting for the earliest copy to finish is an effective method to combat the variability in response time of individual servers. Although adding redundant replicas always reduces service time, the total computing time spent per job may be higher, thus increasing waiting time in queue. The total time spent per job is also proportional to the cost of computing resources. We analyze how different redundancy strategies, for eg. number of replicas, and the time when they are issued and canceled, affect the latency and computing cost. We get the insight that the log-concavity of the service time distribution is a key factor in determining whether adding redundancy reduces latency and cost. If the service distribution is log-convex, then adding maximum redundancy reduces both latency and cost. And if it is log-concave, then having fewer replicas and canceling the redundant requests early is more effective.
AB - In cloud computing systems, assigning a job to multiple servers and waiting for the earliest copy to finish is an effective method to combat the variability in response time of individual servers. Although adding redundant replicas always reduces service time, the total computing time spent per job may be higher, thus increasing waiting time in queue. The total time spent per job is also proportional to the cost of computing resources. We analyze how different redundancy strategies, for eg. number of replicas, and the time when they are issued and canceled, affect the latency and computing cost. We get the insight that the log-concavity of the service time distribution is a key factor in determining whether adding redundancy reduces latency and cost. If the service distribution is log-convex, then adding maximum redundancy reduces both latency and cost. And if it is log-concave, then having fewer replicas and canceling the redundant requests early is more effective.
UR - http://www.scopus.com/inward/record.url?scp=84969849374&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84969849374&partnerID=8YFLogxK
U2 - 10.1109/ALLERTON.2015.7446992
DO - 10.1109/ALLERTON.2015.7446992
M3 - Conference contribution
AN - SCOPUS:84969849374
T3 - 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
SP - 107
EP - 114
BT - 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
Y2 - 29 September 2015 through 2 October 2015
ER -