{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:10Z","timestamp":1750306090725,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T00:00:00Z","timestamp":1497312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-10-LABX-0098"],"award-info":[{"award-number":["ANR-10-LABX-0098"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2017,6,13]]},"abstract":"<jats:p>Distributed storage systems such as Hadoop File System or Google File System (GFS) ensure data availability and durability using replication. Persistence is achieved by replicating the same data block on several nodes, and ensuring that a minimum number of copies are available on the system at any time. Whenever the contents of a node are lost, for instance due to a hard disk crash, the system regenerates the data blocks stored before the failure by transferring them from the remaining replicas. This paper is focused on the analysis of the efficiency of replication mechanism that determines the location of the copies of a given file at some server. The variability of the loads of the nodes of the network is investigated for several policies. Three replication mechanisms are tested against simulations in the context of a real implementation of a such a system: Random, Least Loaded and Power of Choice.<\/jats:p><jats:p>The simulations show that some of these policies may lead to quite unbalanced situations: if \u03b2 is the average number of copies per node it turns out that, at equilibrium, the load of the nodes may exhibit a high variability. It is shown in this paper that a simple variant of a power of choice type algorithm has a striking effect on the loads of the nodes: at equilibrium, the distribution of the load of a node has a bounded support, most of nodes have a load less than 2\u03b2 which is an interesting property for the design of the storage space of these systems. Stochastic models are introduced and investigated to explain this interesting phenomenon.<\/jats:p>","DOI":"10.1145\/3084462","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T18:28:08Z","timestamp":1521829688000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Analysis of a Stochastic Model of Replication in Large Distributed Storage Systems"],"prefix":"10.1145","volume":"1","author":[{"given":"Wen","family":"Sun","sequence":"first","affiliation":[{"name":"INRIA, Paris, France"}]},{"given":"Veronique","family":"Simon","sequence":"additional","affiliation":[{"name":"Sorbonne Universites, UPMC Univ Paris 06, CNRS, INRIA, Paris, France"}]},{"given":"Sebastien","family":"Monnet","sequence":"additional","affiliation":[{"name":"LISTIC - Polytech Annecy-Chambery, Chambery, France"}]},{"given":"Philippe","family":"Robert","sequence":"additional","affiliation":[{"name":"INRIA, Paris, France"}]},{"given":"Pierre","family":"Sens","sequence":"additional","affiliation":[{"name":"Sorbonne Universites, UPMC Univ Paris 06, CNRS, INRIA, Paris, France"}]}],"member":"320","published-online":{"date-parts":[[2017,6,13]]},"reference":[{"volume-title":"Convergence of probability measures","author":"Billingsley P.","key":"e_1_2_1_1_1","unstructured":"P. Billingsley . 1999. Convergence of probability measures ( second ed.). John Wiley & Sons Inc., New York. x+277 pages. A Wiley- Interscience Publication . P. Billingsley. 1999. Convergence of probability measures (second ed.). John Wiley & Sons Inc., New York. x+277 pages. A Wiley- Interscience Publication."},{"key":"e_1_2_1_2_1","volume-title":"HDFS architecture guide. HADOOP APACHE PROJECT http:\/\/hadoop.apache.org\/","author":"Borthakur Dhruba","year":"2008","unstructured":"Dhruba Borthakur . 2008. HDFS architecture guide. HADOOP APACHE PROJECT http:\/\/hadoop.apache.org\/ ( 2008 ). Dhruba Borthakur. 2008. HDFS architecture guide. HADOOP APACHE PROJECT http:\/\/hadoop.apache.org\/ (2008)."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation -","volume":"7","author":"Chang Fay","unstructured":"Fay Chang , Jeffrey Dean , Sanjay Ghemawat , Wilson C. Hsieh , Deborah A. Wallach , Mike Burrows , Tushar Chandra , Andrew Fikes , and Robert E. Gruber . 2006. Bigtable: A Distributed Storage System for Structured Data . In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation - Volume 7 (OSDI'06). USENIX Association, Berkeley, CA, USA, 15--15. Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. 2006. Bigtable: A Distributed Storage System for Structured Data. In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation - Volume 7 (OSDI'06). USENIX Association, Berkeley, CA, USA, 15--15."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1251175.1251182"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_6_1","volume-title":"Kurtz","author":"Ethier Stewart N.","year":"1986","unstructured":"Stewart N. Ethier and Thomas G . Kurtz . 1986 . Markov Processes : Characterization and Convergence. John Wiley & Sons Inc ., New York. x+534 pages. Stewart N. Ethier and Thomas G. Kurtz. 1986. Markov Processes: Characterization and Convergence. John Wiley & Sons Inc., New York. x+534 pages."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/945445.945450"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0021900200015345"},{"key":"e_1_2_1_9_1","unstructured":"M\u00e1rk Jelasity Alberto Montresor Gian Paolo Jesi and Spyros Voulgaris. The Peersim Simulator. http:\/\/peersim.sourceforge.net\/. (????). M\u00e1rk Jelasity Alberto Montresor Gian Paolo Jesi and Spyros Voulgaris. The Peersim Simulator. http:\/\/peersim.sourceforge.net\/. (????)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.2969\/jmsj\/03830543"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"J. F. C. Kingman. 1993. Poisson processes. Oxford studies in probability. J. F. C. Kingman. 1993. Poisson processes. Oxford studies in probability.","DOI":"10.1093\/oso\/9780198536932.001.0001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2240166.2240178"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher Andr\u00e9a W. Richa and Ramesh Sitaraman. 2000. The Power of Two Random Choices: A Survey of Techniques and Results. In in Handbook of Randomized Computing. 255--312. Michael Mitzenmacher Andr\u00e9a W. Richa and Ramesh Sitaraman. 2000. The Power of Two Random Choices: A Survey of Techniques and Results. In in Handbook of Randomized Computing. 255--312.","DOI":"10.1007\/978-1-4615-0013-1_9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/P2P.2009.5284506"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1267903.1267905"},{"key":"e_1_2_1_17_1","volume-title":"Preprint. Proc. ACM Meas. Anal. Comput. Syst.","volume":"1","author":"Robert Philippe","year":"2017","unstructured":"Philippe Robert and Wen Sun . 2017 . An Asymptotic Analysis of Replacement Policies. (2017) . Preprint. Proc. ACM Meas. Anal. Comput. Syst. , Vol. 1 , No. 1, Article 24. Publication date: June 2017. Philippe Robert and Wen Sun. 2017. An Asymptotic Analysis of Replacement Policies. (2017). Preprint. Proc. ACM Meas. Anal. Comput. Syst., Vol. 1, No. 1, Article 24. Publication date: June 2017."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30183-7_11"},{"volume-title":"Foundations","author":"Rogers L. C. G.","key":"e_1_2_1_19_1","unstructured":"L. C. G. Rogers and David Williams . 1994. Diffusions , Markov processes, and martingales . Vol. 1 : Foundations ( second ed.). John Wiley & Sons Ltd ., Chichester. xx+386 pages. L. C. G. Rogers and David Williams. 1994. Diffusions, Markov processes, and martingales. Vol. 1: Foundations (second ed.). John Wiley & Sons Ltd., Chichester. xx+386 pages."},{"key":"e_1_2_1_20_1","volume-title":"Markov processes, and martingales","author":"Rogers L. C. G.","year":"1994","unstructured":"L. C. G. Rogers and David Williams . 2000. Diffusions , Markov processes, and martingales . Vol. 2 . Cambridge University Press , Cambridge . xiv+480 pages. Reprint of the second ( 1994 ) edition. L. C. G. Rogers and David Williams. 2000. Diffusions, Markov processes, and martingales. Vol. 2. Cambridge University Press, Cambridge. xiv+480 pages. Reprint of the second (1994) edition."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/502034.502053"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCA.2015.15"},{"key":"e_1_2_1_23_1","first-page":"20","article-title":"A queueing system with a choice of the shorter 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 . A queueing system with a choice of the shorter of two queues-an asymptotic approach . Problemy Peredachi Informatsii 32 , 1 (1996), 20 -- 34 . N. D. Vvedenskaya, R. L. Dobrushin, and F. I. Karpelevich. 1996. A queueing system with a choice of the shorter of two queues-an asymptotic approach. Problemy Peredachi Informatsii 32, 1 (1996), 20--34.","journal-title":"Problemy Peredachi Informatsii"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084462","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3084462","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:22Z","timestamp":1750217422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3084462"}},"subtitle":["A Mean-Field Approach"],"short-title":[],"issued":{"date-parts":[[2017,6,13]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,6,13]]}},"alternative-id":["10.1145\/3084462"],"URL":"https:\/\/doi.org\/10.1145\/3084462","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2017,6,13]]},"assertion":[{"value":"2017-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}