{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:35:57Z","timestamp":1750221357749,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,2,13]],"date-time":"2018-02-13T00:00:00Z","timestamp":1518480000000},"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":["CIF-1409106, ECCS-1739189, CCF-1718470, CCF-1149860 and CCF-1320416"],"award-info":[{"award-number":["CIF-1409106, ECCS-1739189, CCF-1718470, CCF-1149860 and CCF-1320416"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000774","name":"DTRA","doi-asserted-by":"crossref","award":["HDTRA1-15-1-0003"],"award-info":[{"award-number":["HDTRA1-15-1-0003"]}],"id":[{"id":"10.13039\/100000774","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>We study cloud storage systems with a very large number of files stored in a very large number of servers. In such systems, files are either replicated or coded to ensure reliability, i.e., to guarantee file recovery from server failures. This redundancy in storage can further be exploited to improve system performance (mean file-access delay) through appropriate load-balancing (routing) schemes. However, it is unclear whether coding or replication is better from a system performance perspective since the corresponding queueing analysis of such systems is, in general, quite difficult except for the trivial case when the system load asymptotically tends to zero. Here, we study the more difficult case where the system load is not asymptotically zero. Using the fact that the system size is large, we obtain a mean-field limit for the steady-state distribution of the number of file access requests waiting at each server. We then use the mean-field limit to show that, for a given storage capacity per file, coding strictly outperforms replication at all traffic loads while improving reliability. Further, the factor by which the performance improves in the heavy traffic is at least as large as in the light-traffic case. Finally, we validate these results through extensive simulations.<\/jats:p>","DOI":"10.1145\/3159172","type":"journal-article","created":{"date-parts":[[2018,2,13]],"date-time":"2018-02-13T15:40:40Z","timestamp":1518536440000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Mean-Field Analysis of Coding Versus Replication in Large Data Storage Systems"],"prefix":"10.1145","volume":"3","author":[{"given":"Bin","family":"Li","sequence":"first","affiliation":[{"name":"University of Rhode Island, Kingston"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aditya","family":"Ramamoorthy","sequence":"additional","affiliation":[{"name":"Iowa State University, Ames"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Srikant","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,2,13]]},"reference":[{"volume-title":"Proceedings of the USENIX Conference on Hot Topics in Cloud Computing (HotCloud\u201912)","author":"Ananthanarayanan G.","key":"e_1_2_1_1_1","unstructured":"G. Ananthanarayanan , A. Ghodsi , S. Shenker , and I. Stoica . 2012. Why let resources idle? Aggressive cloning of jobs with Dolly . In Proceedings of the USENIX Conference on Hot Topics in Cloud Computing (HotCloud\u201912) . G. Ananthanarayanan, A. Ghodsi, S. Shenker, and I. Stoica. 2012. Why let resources idle? Aggressive cloning of jobs with Dolly. In Proceedings of the USENIX Conference on Hot Topics in Cloud Computing (HotCloud\u201912)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811039.1811071"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201914)","author":"Chen S.","key":"e_1_2_1_3_1","unstructured":"S. Chen , Y. Sun , U. C. Kozat , L. Huang , P. Sinha , G. Liang , X. Liu , and N. B. Shroff . 2014. When queueing meets coding: Optimal-latency data retrieving scheme in storage clouds . In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201914) . S. Chen, Y. Sun, U. C. Kozat, L. Huang, P. Sinha, G. Liang, X. Liu, and N. B. Shroff. 2014. When queueing meets coding: Optimal-latency data retrieving scheme in storage clouds. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201914)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3216622.3216637"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745844.2745873"},{"volume-title":"Notes for ECE 467: Communication Network Analysis","author":"Hajek B.","key":"e_1_2_1_6_1","unstructured":"B. Hajek . 2006. Notes for ECE 467: Communication Network Analysis . University of Illinois at Urbana-Champaign. B. Hajek. 2006. Notes for ECE 467: Communication Network Analysis. University of Illinois at Urbana-Champaign."},{"volume-title":"Proceedings of the IEEE International Symposium on Information Theory (ISIT\u201912)","author":"Huang L.","key":"e_1_2_1_7_1","unstructured":"L. Huang , S. Pawar , H. Zhang , and K. Ramchandran . 2012. Codes can reduce queueing delay in data centers . In Proceedings of the IEEE International Symposium on Information Theory (ISIT\u201912) . L. Huang, S. Pawar, H. Zhang, and K. Ramchandran. 2012. Codes can reduce queueing delay in data centers. In Proceedings of the IEEE International Symposium on Information Theory (ISIT\u201912)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080091.1080106"},{"volume-title":"Proceedings of the 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 326--333","author":"Joshi G.","key":"e_1_2_1_9_1","unstructured":"G. Joshi , Y. Liu , and E. Soljanin . 2012. Coding for fast content download . In Proceedings of the 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 326--333 . G. Joshi, Y. Liu, and E. Soljanin. 2012. Coding for fast content download. In Proceedings of the 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 326--333."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2014.140518"},{"volume-title":"Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing.","author":"Joshi G.","key":"e_1_2_1_11_1","unstructured":"G. Joshi , E. Soljanin , and G. Wornell . 2015a. Efficient replication of queued tasks to reduce latency in cloud systems . In Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing. G. Joshi, E. Soljanin, and G. Wornell. 2015a. Efficient replication of queued tasks to reduce latency in cloud systems. In Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2825236.2825258"},{"volume-title":"Proceedings of the 2015 IEEE International Symposium on Information Theory (ISIT\u201915)","author":"Kadhe S.","key":"e_1_2_1_13_1","unstructured":"S. Kadhe , E. Soljanin , and A. Sprintson . 2015. Analyzing the download time of availability codes . In Proceedings of the 2015 IEEE International Symposium on Information Theory (ISIT\u201915) . IEEE, 1467--1471. S. Kadhe, E. Soljanin, and A. Sprintson. 2015. Analyzing the download time of availability codes. In Proceedings of the 2015 IEEE International Symposium on Information Theory (ISIT\u201915). IEEE, 1467--1471."},{"key":"e_1_2_1_14_1","unstructured":"D. Knuth R. Graham O. Patashnik and others. 1989. Concrete Mathematics.Adison-Wesley.  D. Knuth R. Graham O. Patashnik and others. 1989. Concrete Mathematics.Adison-Wesley."},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201916)","author":"Li B.","key":"e_1_2_1_15_1","unstructured":"B. Li , A. Ramamoorthy , and R. Srikant . 2016. Mean-field-analysis of coding versus replication in cloud storage systems . In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201916) . B. Li, A. Ramamoorthy, and R. Srikant. 2016. Mean-field-analysis of coding versus replication in cloud storage systems. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201916)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"B. Li A. Ramamoorthy and R. Srikant. 2017. Mean-field-analysis of coding versus replication in cloud storage systems. http:\/\/www.ele.uri.edu\/faculty\/binli\/papers\/StorageCodingReport.pdf.  B. Li A. Ramamoorthy and R. Srikant. 2017. Mean-field-analysis of coding versus replication in cloud storage systems. http:\/\/www.ele.uri.edu\/faculty\/binli\/papers\/StorageCodingReport.pdf.","DOI":"10.1109\/INFOCOM.2016.7524626"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201914)","author":"Liang G.","key":"e_1_2_1_17_1","unstructured":"G. Liang and U. C. Kozat . 2014. TOFEC: Achieving optimal throughput-delay trade-off of cloud storage using erasure codes . In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201914) . G. Liang and U. C. Kozat. 2014. TOFEC: Achieving optimal throughput-delay trade-off of cloud storage using erasure codes. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201914)."},{"key":"e_1_2_1_18_1","unstructured":"S. Lin and D. J. Costello. 2004. Error Control Coding (2nd ed.). Prentice Hall.   S. Lin and D. J. Costello. 2004. Error Control Coding (2nd ed.). Prentice Hall."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2011.07.015"},{"key":"e_1_2_1_20_1","volume-title":"A Note for Stat","author":"Lugo M.","year":"2011","unstructured":"M. Lugo . 2011. A Note for Stat 134 Fall 2011 : The Expectation of the Maximum of Exponentials. University of California at Berkeley. M. Lugo. 2011. A Note for Stat 134 Fall 2011: The Expectation of the Maximum of Exponentials. University of California at Berkeley."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522716"},{"volume-title":"Stochastic Processes","author":"Ross S.","key":"e_1_2_1_23_1","unstructured":"S. Ross . 1995. Stochastic Processes . John Wiley 8 Sons. S. Ross. 1995. Stochastic Processes. John Wiley 8 Sons."},{"volume-title":"Introduction to Probability Models","author":"Ross S.","key":"e_1_2_1_24_1","unstructured":"S. Ross . 2014. Introduction to Probability Models . Academic Press . S. Ross. 2014. Introduction to Probability Models. Academic Press."},{"volume-title":"Proceedings of the Allerton Conference on Communication, Control, and Computing (Allerton).","author":"Shah N. B.","key":"e_1_2_1_25_1","unstructured":"N. B. Shah , K. Lee , and K. Ramchandran . 2013. When do redundant requests reduce latency? In Proceedings of the Allerton Conference on Communication, Control, and Computing (Allerton). N. B. Shah, K. Lee, and K. Ramchandran. 2013. When do redundant requests reduce latency? In Proceedings of the Allerton Conference on Communication, Control, and Computing (Allerton)."},{"volume-title":"Proceedings of the IEEE International Symposium on Information Theory (ISIT\u201914)","author":"Shah N. B.","key":"e_1_2_1_26_1","unstructured":"N. B. Shah , K. Lee , and K. Ramchandran . 2014. The MDS queue: Analysing the latency performance of erasure codes . In Proceedings of the IEEE International Symposium on Information Theory (ISIT\u201914) . N. B. Shah, K. Lee, and K. Ramchandran. 2014. The MDS queue: Analysing the latency performance of erasure codes. In Proceedings of the IEEE International Symposium on Information Theory (ISIT\u201914)."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2636796"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-015-9448-8"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201915)","author":"Sun Y.","key":"e_1_2_1_29_1","unstructured":"Y. Sun , Z. Zheng , C. E. Koksal , K. Kim , and N. B. Shroff . 2015. Provably delay efficient data retrieving in storage clouds . In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201915) . Y. Sun, Z. Zheng, C. E. Koksal, K. Kim, and N. B. Shroff. 2015. Provably delay efficient data retrieving in storage clouds. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201915)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535372.2535392"},{"key":"e_1_2_1_31_1","first-page":"20","article-title":"Queueing system with selection of the shortest of two queues: An asymptotic approach","volume":"32","author":"Vvedenskaya N. D.","year":"1996","unstructured":"N. D. Vvedenskaya , R. L. Dobrushin , and F. I. Karpelevich . 1996 . Queueing system with selection of the shortest of two queues: An asymptotic approach . Probl. Peredachi Inform. 32 , 1 (1996), 20 -- 34 . N. D. Vvedenskaya, R. L. Dobrushin, and F. I. Karpelevich. 1996. Queueing system with selection of the shortest of two queues: An asymptotic approach. Probl. Peredachi Inform. 32, 1 (1996), 20--34.","journal-title":"Probl. Peredachi Inform."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2667522.2667524"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201915)","author":"Ying L.","key":"e_1_2_1_33_1","unstructured":"L. Ying , R. Srikant , and X. Kang . 2015. The power of slightly more than one sample in randomized load balancing . In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201915) . L. Ying, R. Srikant, and X. Kang. 2015. The power of slightly more than one sample in randomized load balancing. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201915)."}],"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\/3159172","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3159172","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3159172","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:11Z","timestamp":1750213571000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3159172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,13]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3159172"],"URL":"https:\/\/doi.org\/10.1145\/3159172","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2018,2,13]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}