{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T20:44:31Z","timestamp":1771015471472,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,4,26]],"date-time":"2017-04-26T00:00:00Z","timestamp":1493164800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1319828"],"award-info":[{"award-number":["CCF-1319828"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"AFOSR","doi-asserted-by":"crossref","award":["FA9550-11-1-0183"],"award-info":[{"award-number":["FA9550-11-1-0183"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Schlumberger Faculty for the Future Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>In cloud computing systems, assigning a task 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 and reduce latency. But adding redundancy may result in higher cost of computing resources, as well as an increase in queueing delay due to higher traffic load. This work helps in understanding when and how redundancy gives a cost-efficient reduction in latency. For a general task service time distribution, we compare different redundancy strategies in terms of the number of redundant tasks and the time when they are issued and canceled. We get the insight that the log-concavity of the task service time creates a dichotomy of when adding redundancy helps. If the service time distribution is log-convex (i.e., log of the tail probability is convex), then adding maximum redundancy reduces both latency and cost. And if it is log-concave (i.e., log of the tail probability is concave), then less redundancy, and early cancellation of redundant tasks is more effective. Using these insights, we design a general redundancy strategy that achieves a good latency-cost trade-off for an arbitrary service time distribution. This work also generalizes and extends some results in the analysis of fork-join queues.<\/jats:p>","DOI":"10.1145\/3055281","type":"journal-article","created":{"date-parts":[[2017,4,28]],"date-time":"2017-04-28T12:38:23Z","timestamp":1493383103000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":94,"title":["Efficient Redundancy Techniques for Latency Reduction in Cloud Systems"],"prefix":"10.1145","volume":"2","author":[{"given":"Gauri","family":"Joshi","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh PA"}]},{"given":"Emina","family":"Soljanin","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway NJ"}]},{"given":"Gregory","family":"Wornell","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Massachusetts Ave, Cambridge MA"}]}],"member":"320","published-online":{"date-parts":[[2017,4,26]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 2013 USENIX Conference on Networked Systems Design and Implementation. 185--198","author":"Ananthanarayanan Ganesh","year":"2013"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-004-0514-4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.2307\/3214882"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 2014 IEEE International Conference on Communications.","author":"Chen Shengbo"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2408776.2408794"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177698701"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0144074"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139626514"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745844.2745873"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","volume-title":"Performance Modeling and Design of Computer Systems: Queueing Theory in Action","author":"Harchol-Balter Mor","DOI":"10.1017\/CBO9781139226424"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 2012 Allerton Conference on Communication, Control, and Computing. 326--333","author":"Joshi G."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2014.140518"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2825236.2825258"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"G. Kabatiansky E. Krouk and S. Semenov (Eds.). 2005. Coding of messages at the transport layer of the data network. In Error Correcting Coding and Security for Data Networks: Analysis of the Superchannel Concept. Wiley 191--211.  G. Kabatiansky E. Krouk and S. Semenov (Eds.). 2005. Coding of messages at the transport layer of the data network. In Error Correcting Coding and Security for Data Networks: Analysis of the Superchannel Concept. Wiley 191--211.","DOI":"10.1002\/0470867574.ch7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2015.7282699"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1246886623"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-007-0018-8"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 2014 IEEE Global Communications Conference (GLOBECOM\u201914)","author":"Kumar A."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1959.5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2014.6848010"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 1975 International Conference on Communications (ICC\u201975)","author":"Maxemchuk N. F.","year":"1975"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.2213"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522716"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2013.6736597"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2014.6874955"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 2015 IEEE Conference on Computer Communications (INFOCOM\u201915)","author":"Sun Yin"},{"key":"e_1_2_1_29_1","volume-title":"Retrieved","author":"Varki Elizabeth","year":"2008"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-011-9274-6"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535372.2535392"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591971.2592042"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847220.2847223"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2667522.2667524"}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055281","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055281","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055281","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:37Z","timestamp":1750217797000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055281"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,26]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/3055281"],"URL":"https:\/\/doi.org\/10.1145\/3055281","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"value":"2376-3639","type":"print"},{"value":"2376-3647","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,26]]},"assertion":[{"value":"2015-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}