Mean Field and Refined Mean Field Approximations for Heterogeneous Systems: It Works! - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Proceedings of the ACM on Measurement and Analysis of Computing Systems Année : 2022

Mean Field and Refined Mean Field Approximations for Heterogeneous Systems: It Works!

Résumé

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.
Fichier principal
Vignette du fichier
AllmeierGast_HeterogeneousMeanField.pdf (1.01 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03600672 , version 1 (07-03-2022)

Identifiants

Citer

Sebastian Allmeier, Nicolas Gast. Mean Field and Refined Mean Field Approximations for Heterogeneous Systems: It Works!. Proceedings of the ACM on Measurement and Analysis of Computing Systems , 2022, 6 (1), pp.1-43. ⟨10.1145/3508033⟩. ⟨hal-03600672⟩
84 Consultations
199 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More