{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T02:26:05Z","timestamp":1771640765516,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T00:00:00Z","timestamp":1645660800000},"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-19-CE23-0015"],"award-info":[{"award-number":["ANR-19-CE23-0015"]}],"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":[[2022,2,24]]},"abstract":"<jats:p>Mean field approximation is a powerful technique to study the performance of large stochastic systems represented as n interacting objects. Applications include load balancing models, epidemic spreading, cache replacement policies, or large-scale data centers. Mean field approximation is asymptotically exact for systems composed of n homogeneous objects under mild conditions. In this paper, we study what happens when objects are heterogeneous. This can represent servers with different speeds or contents with different popularities. We define an interaction model that allows obtaining asymptotic convergence results for stochastic systems with heterogeneous object behavior, and show that the error of the mean field approximation is of order $O(1\/n)$. More importantly, we show how to adapt the refined mean field approximation, developed by Gast et al., and show that the error of this approximation is reduced to O(1\/n^2). To illustrate the applicability of our result, we present two examples. The first addresses a list-based cache replacement model, RANDOM(m), which is an extension of the RANDOM policy. The second is a heterogeneous supermarket model. These examples show that the proposed approximations are computationally tractable and very accurate. They also show that for moderate system sizes (30) the refined mean field approximation tends to be more accurate than simulations for any reasonable simulation time.<\/jats:p>","DOI":"10.1145\/3508033","type":"journal-article","created":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T23:44:29Z","timestamp":1646091869000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Mean Field and Refined Mean Field Approximations for Heterogeneous Systems"],"prefix":"10.1145","volume":"6","author":[{"given":"Sebastian","family":"Allmeier","sequence":"first","affiliation":[{"name":"Univ. Grenoble Alpes, Inria, CNRS, 38000 Grenoble, France"}]},{"given":"Nicolas","family":"Gast","sequence":"additional","affiliation":[{"name":"Univ. Grenoble Alpes, Inria, CNRS, 38000 Grenoble, France"}]}],"member":"320","published-online":{"date-parts":[[2022,2,28]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"TOSME 2021 .","author":"Allmeier Sebastian","year":"2021","unstructured":", Sebastian Allmeier and Nicolas Gast . 2021 . rmftool-A library to Compute (Refined) Mean Field Approximation (s) . In TOSME 2021 . , Sebastian Allmeier and Nicolas Gast. 2021. rmftool-A library to Compute (Refined) Mean Field Approximation (s). In TOSME 2021 ."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1243877"},{"key":"e_1_2_1_3_1","volume-title":"Stein's method for steady-state diffusion approximations . Ph.,D. Dissertation","author":"Braverman Anton","unstructured":", Anton Braverman . 2017. Stein's method for steady-state diffusion approximations . Ph.,D. Dissertation . Cornell University . , Anton Braverman. 2017. Stein's method for steady-state diffusion approximations . Ph.,D. Dissertation. Cornell University."},{"key":"e_1_2_1_4_1","volume-title":"Anton Braverman and Jim Dai","year":"2017","unstructured":", Anton Braverman and Jim Dai . 2017 . Stein's method for steady-state diffusion approximations of $ M\/Ph\/ n , Anton Braverman and Jim Dai. 2017. Stein's method for steady-state diffusion approximations of $ M\/Ph\/n"},{"key":"e_1_2_1_5_1","volume-title":"The Annals of Applied Probability","author":"M","year":"2017","unstructured":"M $ systems. The Annals of Applied Probability , Vol. 27 , 1 ( 2017 ), 550--581. M $ systems. The Annals of Applied Probability , Vol. 27, 1 (2017), 550--581."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/15-SSY212"},{"key":"e_1_2_1_7_1","volume-title":"High Order Steady-State Diffusion Approximations. arXiv:2012.02824 (Dec","author":"Braverman Anton","year":"2020","unstructured":"020)]% bravermanHighOrderSteadystate2020, Anton Braverman , J. G. Dai , and Xiao Fang . 2020. High Order Steady-State Diffusion Approximations. arXiv:2012.02824 (Dec . 2020 ). arxiv: 2012.02824 020)]% bravermanHighOrderSteadystate2020, Anton Braverman, J. G. Dai, and Xiao Fang. 2020. High Order Steady-State Diffusion Approximations. arXiv:2012.02824 (Dec. 2020). arxiv: 2012.02824"},{"key":"e_1_2_1_8_1","volume-title":"Giuliano Casale and Nicolas Gast","year":"2020","unstructured":", Giuliano Casale and Nicolas Gast . 2020 . Performance analysis methods for list-based caches with non-uniform access. IEEE\/ACM Transactions on Networking ( 2020). , Giuliano Casale and Nicolas Gast. 2020. Performance analysis methods for list-based caches with non-uniform access. IEEE\/ACM Transactions on Networking (2020)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2001.916637"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/98457.98525"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2018.06.007"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(77)80014-7"},{"key":"e_1_2_1_13_1","volume-title":"A versatile and accurate approximation for LRU cache performance. In 2012 24th international teletraffic congress (ITC 24)","author":"Fricker Christine","unstructured":"012)]% fricker2012versatile, Christine Fricker , Philippe Robert , and James Roberts . 2012. A versatile and accurate approximation for LRU cache performance. In 2012 24th international teletraffic congress (ITC 24) . IEEE , 1--8. 012)]% fricker2012versatile, Christine Fricker, Philippe Robert, and James Roberts. 2012. A versatile and accurate approximation for LRU cache performance. In 2012 24th international teletraffic congress (ITC 24). IEEE, 1--8."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3084454"},{"key":"e_1_2_1_15_1","volume-title":"Performance Evaluation","volume":"129","author":"Gast Nicolas","year":"2019","unstructured":"019)]% gastSizeExpansionsMean2019, Nicolas Gast , Luca Bortolussi , and Mirco Tribastone . 2019 . Size Expansions of Mean Field Approximation: Transient and Steady-State Analysis . Performance Evaluation , Vol. 129 (Feb. 2019), 60--80. https:\/\/doi.org\/10.1016\/j.peva.2018.09.005 10.1016\/j.peva.2018.09.005 019)]% gastSizeExpansionsMean2019, Nicolas Gast, Luca Bortolussi, and Mirco Tribastone. 2019. Size Expansions of Mean Field Approximation: Transient and Steady-State Analysis. Performance Evaluation , Vol. 129 (Feb. 2019), 60--80. https:\/\/doi.org\/10.1016\/j.peva.2018.09.005"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745844.2745850"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154491"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154491"},{"key":"#cr-split#-e_1_2_1_19_1.1","doi-asserted-by":"crossref","unstructured":"020)]% gomesIndividualVariationSusceptibility2020 M. Gabriela M. Gomes Ricardo Aguas Rodrigo M. Corder Jessica G. King Kate E. Langwig Caetano Souto-Maior Jorge Carneiro Marcelo U. Ferreira and Carlos Penha-Gonc calves. 2020. Individual Variation in Susceptibility or Exposure to SARS -CoV -2 Lowers the Herd Immunity Threshold . Preprint. Epidemiology . https:\/\/doi.org\/10.1101\/2020.04.27.20081893 10.1101\/2020.04.27.20081893","DOI":"10.1101\/2020.04.27.20081893"},{"key":"#cr-split#-e_1_2_1_19_1.2","doi-asserted-by":"crossref","unstructured":"020)]% gomesIndividualVariationSusceptibility2020 M. Gabriela M. Gomes Ricardo Aguas Rodrigo M. Corder Jessica G. King Kate E. Langwig Caetano Souto-Maior Jorge Carneiro Marcelo U. Ferreira and Carlos Penha-Gonc calves. 2020. Individual Variation in Susceptibility or Exposure to SARS -CoV -2 Lowers the Herd Immunity Threshold . Preprint. Epidemiology . https:\/\/doi.org\/10.1101\/2020.04.27.20081893","DOI":"10.1101\/2020.04.27.20081893"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.3454685"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"The Journal of Chemical Physics 2011 135 Ramon Grima Philipp Thomas and Arthur V. Straube. 2011. How accurate are the nonlinear chemical Fokker-Planck and chemical Langevin equations","DOI":"10.1063\/1.3625958"},{"key":"e_1_2_1_22_1","volume-title":"Stochastic Analysis of Computer Storage","author":"Hazewinkel M","unstructured":"987)]% hazewinkelStochasticAnalysisComputer1987, M Hazewinkel , F Calogero , Yu. I Manin , A. H. G Rinnooy Kan , and G.-C Rota . 1987. Stochastic Analysis of Computer Storage . Springer Netherlands , Dordrecht . 987)]% hazewinkelStochasticAnalysisComputer1987, M Hazewinkel, F Calogero, Yu. I Manin, A. H. G Rinnooy Kan, and G.-C Rota. 1987. Stochastic Analysis of Computer Storage .Springer Netherlands , Dordrecht ."},{"key":"e_1_2_1_23_1","volume-title":"Analysis of Page Replacement Policies in the Fluid Limit. Oper. Res.","volume":"58","author":"Hirade R.","year":"2010","unstructured":", R. Hirade and T. Osogami . 2010 . Analysis of Page Replacement Policies in the Fluid Limit. Oper. Res. , Vol. 58 ( July 2010 ), 971--984. https:\/\/doi.org\/10.1287\/opre.1090.0761 10.1287\/opre.1090.0761 , R. Hirade and T. Osogami. 2010. Analysis of Page Replacement Policies in the Fluid Limit. Oper. Res. , Vol. 58 (July 2010), 971--984. https:\/\/doi.org\/10.1287\/opre.1090.0761"},{"key":"e_1_2_1_24_1","volume-title":"Normal approximations for discrete-time occupancy processes. Stochastic Processes and their Applications","author":"Hodgkinson Liam","year":"2020","unstructured":"020)]% hodgkinsonNormalApproximationsDiscretetime2018, Liam Hodgkinson , Ross McVinish , and Philip K Pollett . 2020. Normal approximations for discrete-time occupancy processes. Stochastic Processes and their Applications , Vol. 130 , 10 ( 2020 ), 6414--6444. 020)]% hodgkinsonNormalApproximationsDiscretetime2018, Liam Hodgkinson, Ross McVinish, and Philip K Pollett. 2020. Normal approximations for discrete-time occupancy processes. Stochastic Processes and their Applications , Vol. 130, 10 (2020), 6414--6444."},{"key":"e_1_2_1_25_1","first-page":"1","article-title":"onvergence, Bo Jiang, Philippe Nain, and Don Towsley. 2018. On the convergence of the TTL approximation for an LRU cache under independent stationary request processes","volume":"3","year":"2018","unstructured":"018)]% jiang 2018 c onvergence, Bo Jiang, Philippe Nain, and Don Towsley. 2018. On the convergence of the TTL approximation for an LRU cache under independent stationary request processes . ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS) , Vol. 3 , 4 (2018), 1 -- 31 . 018)]% jiang2018convergence, Bo Jiang, Philippe Nain, and Don Towsley. 2018. On the convergence of the TTL approximation for an LRU cache under independent stationary request processes. ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS) , Vol. 3, 4 (2018), 1--31.","journal-title":"ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS)"},{"key":"e_1_2_1_26_1","volume-title":"Mean Field Games and Nonlinear Markov Processes. arXiv:1112.3744 (April","author":"Kolokoltsov Vassili N.","year":"2012","unstructured":"012)]% kolokoltsovMeanFieldGames2012, Vassili N. Kolokoltsov , Jiajie Li , and Wei Yang . 2012. Mean Field Games and Nonlinear Markov Processes. arXiv:1112.3744 (April 2012 ). arxiv: 1112.3744 012)]% kolokoltsovMeanFieldGames2012, Vassili N. Kolokoltsov, Jiajie Li, and Wei Yang. 2012. Mean Field Games and Nonlinear Markov Processes. arXiv:1112.3744 (April 2012). arxiv: 1112.3744"},{"key":"e_1_2_1_27_1","volume-title":"Strong Approximation Theorems for Density Dependent Markov Chains. Stochastic Processes and their Applications","author":"Kurtz Thomas G.","year":"1978","unstructured":", Thomas G. Kurtz . 1978. Strong Approximation Theorems for Density Dependent Markov Chains. Stochastic Processes and their Applications , Vol. 6 , 3 ( Feb. 1978 ), 223--240. https:\/\/doi.org\/10.1016\/0304--4149(78)90020-0 10.1016\/0304--4149(78)90020-0 , Thomas G. Kurtz. 1978. Strong Approximation Theorems for Density Dependent Markov Chains. Stochastic Processes and their Applications , Vol. 6, 3 (Feb. 1978), 223--240. https:\/\/doi.org\/10.1016\/0304--4149(78)90020-0"},{"key":"e_1_2_1_28_1","volume-title":"Marc M\u00e9zard, Giorgio Parisi, and Miguel Angel Virasoro.","year":"1987","unstructured":"rd mbox.(1987)]% mezard1987sk , Marc M\u00e9zard, Giorgio Parisi, and Miguel Angel Virasoro. 1987 . Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications. World Scientific Publishing Company ( 1987), 232--237. rd et almbox.(1987)]% mezard1987sk, Marc M\u00e9zard, Giorgio Parisi, and Miguel Angel Virasoro. 1987. Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications. World Scientific Publishing Company (1987), 232--237."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.963420"},{"key":"e_1_2_1_30_1","volume-title":"Herd Immunity under Individual Variation and Reinfection. arXiv:2008.00098 (Nov","author":"Montalb\u00e1n Antonio","year":"2020","unstructured":"Antonio Montalb\u00e1n , Rodrigo M. Corder , and M. Gabriela M. Gomes . 2020. Herd Immunity under Individual Variation and Reinfection. arXiv:2008.00098 (Nov . 2020 ). arxiv: 2008.00098 et almbox.(2020)]% montalbanHerdImmunityIndividual2020, Antonio Montalb\u00e1n, Rodrigo M. Corder, and M. Gabriela M. Gomes. 2020. Herd Immunity under Individual Variation and Reinfection. arXiv:2008.00098 (Nov. 2020). arxiv: 2008.00098"},{"key":"e_1_2_1_31_1","volume-title":"Arpan Mukhopadhyay and Ravi R. Mazumdar","year":"2015","unstructured":", Arpan Mukhopadhyay and Ravi R. Mazumdar . 2015 . Analysis of Load Balancing in Large Heterogeneous Processor Sharing Systems . arXiv:1311.5806 (Feb. 2015). arxiv: 1311.5806 , Arpan Mukhopadhyay and Ravi R. Mazumdar. 2015. Analysis of Load Balancing in Large Heterogeneous Processor Sharing Systems. arXiv:1311.5806 (Feb. 2015). arxiv: 1311.5806"},{"key":"e_1_2_1_32_1","first-page":"i","article-title":"Approximate computation of expectations","volume":"7","author":"Stein Charles","year":"1986","unstructured":", Charles Stein . 1986 . Approximate computation of expectations . Lecture Notes-Monograph Series , Vol. 7 (1986), i -- 164 . , Charles Stein. 1986. Approximate computation of expectations. Lecture Notes-Monograph Series , Vol. 7 (1986), i--164.","journal-title":"Lecture Notes-Monograph Series"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2012.05.008"},{"key":"e_1_2_1_34_1","first-page":"1","article-title":"A Mean Field Model for a Class of Garbage Collection Algorithms in Flash-Based Solid State Drives","volume":"41","author":"Houdt Benny Van","year":"2013","unstructured":", Benny Van Houdt . 2013 . A Mean Field Model for a Class of Garbage Collection Algorithms in Flash-Based Solid State Drives . ACM SIGMETRICS Performance Evaluation Review , Vol. 41 , 1 (June 2013), 191--202. https:\/\/doi.org\/10.1145\/2494232.2465543 10.1145\/2494232.2465543 , Benny Van Houdt. 2013. A Mean Field Model for a Class of Garbage Collection Algorithms in Flash-Based Solid State Drives. ACM SIGMETRICS Performance Evaluation Review , Vol. 41, 1 (June 2013), 191--202. https:\/\/doi.org\/10.1145\/2494232.2465543","journal-title":"ACM SIGMETRICS Performance Evaluation Review"},{"key":"e_1_2_1_35_1","volume-title":"Stochastic processes in physics and chemistry","author":"van Kampen N. G.","unstructured":", N. G. van Kampen . 2007. Stochastic processes in physics and chemistry . Elsevier , Amsterdam; Boston; London . , N. G. van Kampen. 2007. Stochastic processes in physics and chemistry .Elsevier, Amsterdam; Boston; London."},{"key":"e_1_2_1_36_1","volume-title":"On the Rate of Convergence of Mean-Field Models: Stein's Method Meets the Perturbation Theory. arXiv preprint arXiv:1510.00761","author":"Ying Lei","year":"2015","unstructured":", Lei Ying . 2015. On the Rate of Convergence of Mean-Field Models: Stein's Method Meets the Perturbation Theory. arXiv preprint arXiv:1510.00761 ( 2015 ). , Lei Ying. 2015. On the Rate of Convergence of Mean-Field Models: Stein's Method Meets the Perturbation Theory. arXiv preprint arXiv:1510.00761 (2015)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896377.2901463"}],"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\/3508033","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3508033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:29Z","timestamp":1750191149000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3508033"}},"subtitle":["It Works!"],"short-title":[],"issued":{"date-parts":[[2022,2,24]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2,24]]}},"alternative-id":["10.1145\/3508033"],"URL":"https:\/\/doi.org\/10.1145\/3508033","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,24]]},"assertion":[{"value":"2022-02-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}