Loading [MathJax]/jax/output/SVG/jax.js
Search Advanced

Networks and Heterogeneous Media

2010, Volume 5, Issue 1: 31-62. doi: 10.3934/nhm.2010.5.31
Previous Article Next Article

A particle system in interaction with a rapidly varying environment: Mean field limits and applications

  • 1.
    Institut de Mathématiques de Toulouse, CNRS & Université de Toulouse, 31062 Toulouse cedex 9
  • 2.
    Department of Mathematics and Statistics, University of Ottawa, 585 King Edward Avenue, Ottawa, Ontario K1N 6M8
  • 3.
    Microsoft Reasearch, Roger Needham Building, 7 J J Thomson Avenue, Cambridge, CB3 0FB
  • Received: 01 February 2009 Revised: 01 November 2009

  • Primary: 60K35; Secondary: 60K37.

  • We study an interacting particle system whose dynamics depends on an interacting random environment. As the number of particles grows large, the transition rate of the particles slows down (perhaps because they share a common resource of fixed capacity). The transition rate of a particle is determined by its state, by the empirical distribution of all the particles and by a rapidly varying environment. The transitions of the environment are determined by the empirical distribution of the particles. We prove the propagation of chaos on the path space of the particles and establish that the limiting trajectory of the empirical measure of the states of the particles satisfies a deterministic differential equation. This deterministic differential equation involves the time averages of the environment process.
       We apply the results on particle systems to understand the behavior of computer networks where users access a shared resource using a distributed random Medium Access Control (MAC) algorithm. MAC algorithms are used in all Local Area Network (LAN), and have been notoriously difficult to analyze. Our analysis allows us to provide simple and explicit expressions of the network performance under such algorithms.

    Citation: Charles Bordenave, David R. McDonald, Alexandre Proutière. A particle system in interaction with a rapidly varying environment: Mean field limits and applications[J]. Networks and Heterogeneous Media, 2010, 5(1): 31-62. doi: 10.3934/nhm.2010.5.31

    Related Papers:

    [1] Charles Bordenave, David R. McDonald, Alexandre Proutière . A particle system in interaction with a rapidly varying environment: Mean field limits and applications. Networks and Heterogeneous Media, 2010, 5(1): 31-62. doi: 10.3934/nhm.2010.5.31
    [2] Fabio Camilli, Italo Capuzzo Dolcetta, Maurizio Falcone . Preface. Networks and Heterogeneous Media, 2012, 7(2): i-ii. doi: 10.3934/nhm.2012.7.2i
    [3] Michele Gianfelice, Enza Orlandi . Dynamics and kinetic limit for a system of noiseless d-dimensional Vicsek-type particles. Networks and Heterogeneous Media, 2014, 9(2): 269-297. doi: 10.3934/nhm.2014.9.269
    [4] Michael Herty, Lorenzo Pareschi, Giuseppe Visconti . Mean field models for large data–clustering problems. Networks and Heterogeneous Media, 2020, 15(3): 463-487. doi: 10.3934/nhm.2020027
    [5] Maria Teresa Chiri, Xiaoqian Gong, Benedetto Piccoli . Mean-field limit of a hybrid system for multi-lane car-truck traffic. Networks and Heterogeneous Media, 2023, 18(2): 723-752. doi: 10.3934/nhm.2023031
    [6] Nastassia Pouradier Duteil . Mean-field limit of collective dynamics with time-varying weights. Networks and Heterogeneous Media, 2022, 17(2): 129-161. doi: 10.3934/nhm.2022001
    [7] Michael Herty, Lorenzo Pareschi, Sonja Steffensen . Mean--field control and Riccati equations. Networks and Heterogeneous Media, 2015, 10(3): 699-715. doi: 10.3934/nhm.2015.10.699
    [8] Yves Achdou, Victor Perez . Iterative strategies for solving linearized discrete mean field games systems. Networks and Heterogeneous Media, 2012, 7(2): 197-217. doi: 10.3934/nhm.2012.7.197
    [9] Seung-Yeal Ha, Jeongho Kim, Jinyeong Park, Xiongtao Zhang . Uniform stability and mean-field limit for the augmented Kuramoto model. Networks and Heterogeneous Media, 2018, 13(2): 297-322. doi: 10.3934/nhm.2018013
    [10] András Bátkai, Istvan Z. Kiss, Eszter Sikolya, Péter L. Simon . Differential equation approximations of stochastic network processes: An operator semigroup approach. Networks and Heterogeneous Media, 2012, 7(1): 43-58. doi: 10.3934/nhm.2012.7.43
  • We study an interacting particle system whose dynamics depends on an interacting random environment. As the number of particles grows large, the transition rate of the particles slows down (perhaps because they share a common resource of fixed capacity). The transition rate of a particle is determined by its state, by the empirical distribution of all the particles and by a rapidly varying environment. The transitions of the environment are determined by the empirical distribution of the particles. We prove the propagation of chaos on the path space of the particles and establish that the limiting trajectory of the empirical measure of the states of the particles satisfies a deterministic differential equation. This deterministic differential equation involves the time averages of the environment process.
       We apply the results on particle systems to understand the behavior of computer networks where users access a shared resource using a distributed random Medium Access Control (MAC) algorithm. MAC algorithms are used in all Local Area Network (LAN), and have been notoriously difficult to analyze. Our analysis allows us to provide simple and explicit expressions of the network performance under such algorithms.


  • This article has been cited by:

    1. Christina Vlachou, Albert Banchs, Julien Herzen, Patrick Thiran, How CSMA/CA With Deferral Affects Performance and Dynamics in Power-Line Communications, 2017, 25, 1063-6692, 250, 10.1109/TNET.2016.2580642
    2. Jeong-woo Cho, Jean-Yves Le Boudec, Yuming Jiang, On the Asymptotic Validity of the Decoupling Assumption for Analyzing 802.11 MAC Protocol, 2012, 58, 0018-9448, 6879, 10.1109/TIT.2012.2208582
    3. Luca Bortolussi, Mirco Tribastone, 2012, Fluid limits of queueing networks with batches, 9781450312028, 45, 10.1145/2188286.2188296
    4. Luca Bortolussi, Jane Hillston, Diego Latella, Mieke Massink, Continuous approximation of collective system behaviour: A tutorial, 2013, 70, 01665316, 317, 10.1016/j.peva.2013.01.001
    5. Giuliano Casale, Mirco Tribastone, Peter G. Harrison, Blending randomness in closed queueing network models, 2014, 82, 01665316, 15, 10.1016/j.peva.2014.09.001
    6. Santiago Duran, Ina Maria Verloop, Asymptotic Optimal Control of Markov-Modulated Restless Bandits, 2019, 46, 0163-5999, 44, 10.1145/3292040.3219636
    7. Jiaming Xu, Bruce Hajek, The Supermarket Game, 2013, 3, 1946-5238, 405, 10.1287/12-SSY093
    8. Luca Bortolussi, Richard A. Hayden, Bounds on the deviation of discrete-time Markov chains from their mean-field model, 2013, 70, 01665316, 736, 10.1016/j.peva.2013.08.012
    9. Sarath Yasodharan, Rajesh Sundaresan, Large-time behaviour and the second eigenvalue problem for finite-state mean-field interacting particle systems, 2023, 55, 0001-8678, 85, 10.1017/apr.2022.11
    10. Jeong-woo Cho, Jean-Yves Le Boudec, Yuming Jiang, On the validity of the fixed point equation and decoupling assumption for analyzing the 802.11 mac protocol, 2010, 38, 0163-5999, 36, 10.1145/1870178.1870191
    11. Jiaming Xu, Bruce Hajek, 2012, The supermarket game, 978-1-4673-2579-0, 2511, 10.1109/ISIT.2012.6283969
    12. Yang Zhang, Edwin K. P. Chong, Jan Hannig, Donald Estep, Approximating Extremely Large Networks via Continuum Limits, 2013, 1, 2169-3536, 577, 10.1109/ACCESS.2013.2281668
    13. Vivek Shripad Borkar, Rajesh Sundaresan, 2011, Asymptotics of the invariant measure in mean field models with jumps, 978-1-4577-1817-5, 1258, 10.1109/Allerton.2011.6120312
    14. Lei Ying, Stein's Method for Mean Field Approximations in Light and Heavy Traffic Regimes, 2017, 1, 2476-1249, 1, 10.1145/3084449
    15. Santiago Duran, Ina Maria Verloop, Asymptotic Optimal Control of Markov-Modulated Restless Bandits, 2019, 46, 01635999, 44, 10.1145/3308809.3308835
    16. Nicolas Gast, Bruno Gaujal, A mean field approach for optimization in discrete time, 2011, 21, 0924-6703, 63, 10.1007/s10626-010-0094-3
    17. 2013, 978-3-031-79259-5, 10.1007/978-3-031-79260-1
    18. Howard H. Yang, Ahmed Arafa, Tony Q. S. Quek, H. Vincent Poor, Spatiotemporal Analysis for Age of Information in Random Access Networks Under Last-Come First-Serve With Replacement Protocol, 2022, 21, 1536-1276, 2813, 10.1109/TWC.2021.3116041
    19. Chithrupa Ramesh, Henrik Sandberg, Karl H. Johansson, Performance Analysis of a Network of Event-Based Systems, 2016, 61, 0018-9286, 3568, 10.1109/TAC.2016.2523422
    20. Naoki Tsukada, Ryo Hirade, Naoto Miyoshi, Fluid limit analysis of FIFO and RR caching for independent reference models, 2012, 69, 01665316, 403, 10.1016/j.peva.2012.05.008
    21. Shiba Biswal, Karthik Elamvazhuthi, Spring Berman, Decentralized Control of Multiagent Systems Using Local Density Feedback, 2022, 67, 0018-9286, 3920, 10.1109/TAC.2021.3109520
    22. Ling Luo, Zhenyu Liu, Zhiyong Chen, Min Hua, Wenqing Li, Bin Xia, Age of Information-Based Scheduling for Wireless D2D Systems With a Deep Learning Approach, 2022, 6, 2473-2400, 1875, 10.1109/TGCN.2022.3149486
    23. Michel Benaim, Jean-Yves Le Boudec, 2008, A class of mean field interaction models for computer and communication systems, 589, 10.1109/WIOPT.2008.4586140
    24. Sebastian Allmeier, Nicolas Gast, Bias and Refinement of Multiscale Mean Field Models, 2023, 7, 2476-1249, 1, 10.1145/3579336
    25. Santiago Duran, Ina Maria Verloop, 2018, Asymptotic Optimal Control of Markov-Modulated Restless Bandits, 9781450358460, 44, 10.1145/3219617.3219636
    26. Sarath Yasodharan, Rajesh Sundaresan, 2021, The Four Levels of Fixed-Points in Mean-Field Models, 978-1-6654-4177-3, 1, 10.1109/NCC52529.2021.9530179
    27. Lei Ying, 2016, On the Approximation Error of Mean-Field Models, 9781450342667, 285, 10.1145/2896377.2901463
    28. Charles Bordenave, David McDonald, Alexandre Proutiere, Asymptotic Stability Region of Slotted Aloha, 2012, 58, 0018-9448, 5841, 10.1109/TIT.2012.2201333
    29. Sylvain Gibaud, Jörgen Weibull, The dynamics of fitness and wealth distributions — a stochastic game-theoretic model, 2022, 9, 2164-6066, 405, 10.3934/jdg.2022016
    30. Jean-Yves Le Boudec, The stationary behaviour of fluid limits of reversible processes is concentrated on stationary points, 2013, 8, 1556-181X, 529, 10.3934/nhm.2013.8.529
    31. Lei Ying, On the Approximation Error of Mean-Field Models, 2018, 8, 1946-5238, 126, 10.1287/stsy.2018.0012
    32. Laura Aspirot, Ernesto Mordecki, Gerardo Rubino, 2011, Fluid Limits Applied to Peer to Peer Network Analysis, 978-1-4577-0973-9, 13, 10.1109/QEST.2011.11
    33. Lei Ying, On the Approximation Error of Mean-Field Models, 2016, 44, 0163-5999, 285, 10.1145/2964791.2901463
    34. Ahmad AlAmmouri, Jeffrey G. Andrews, Francois Baccelli, 2019, Stability of Wireless Random Access Systems, 978-1-7281-3151-1, 1190, 10.1109/ALLERTON.2019.8919898
    35. Amarjit Budhiraja, Michael Conroy, Empirical Measure and Small Noise Asymptotics Under Large Deviation Scaling for Interacting Diffusions, 2022, 35, 0894-9840, 295, 10.1007/s10959-020-01071-4
    36. Vivek S. Borkar, Rajesh Sundaresan, Asymptotics of the Invariant Measure in Mean Field Models with Jumps, 2012, 2, 1946-5238, 322, 10.1287/12-SSY064
    37. Sarath Yasodharan, Rajesh Sundaresan, Large deviations of mean-field interacting particle systems in a fast varying environment, 2022, 32, 1050-5164, 10.1214/21-AAP1718
    38. Andrea Baiocchi, Ion Turcanu, Alexey Vinel, Age of Information in CSMA-Based Networks With Bursty Update Traffic, 2022, 10, 2169-3536, 44088, 10.1109/ACCESS.2022.3168321
    39. Ravi R. Mazumdar, 2013, Chapter 4, 978-3-031-79259-5, 107, 10.1007/978-3-031-79260-1_4
    40. Nicolas Gast, Bruno Gaujal, Markov chains with discontinuous drifts have differential inclusion limits, 2012, 69, 01665316, 623, 10.1016/j.peva.2012.07.003
    41. Jeong-Woo Cho, Yuming Jiang, Fundamentals of the Backoff Process in 802.11: Dichotomy of the Aggregation, 2015, 61, 0018-9448, 1687, 10.1109/TIT.2015.2404795
    42. Sebastian Allmeier, Nicolas Gast, 2023, Bias and Refinement of Multiscale Mean Field Models, 9798400700743, 29, 10.1145/3578338.3593527
    43. Sebastian Allmeier, Nicolas Gast, Bias and Refinement of Multiscale Mean Field Models, 2023, 51, 0163-5999, 29, 10.1145/3606376.3593527
  • Reader Comments
  • © 2010 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
Networks and Heterogeneous Media
1.2 1.9

Metrics

Article views(4370) PDF downloads(95) Cited by(43)

Preview PDF
Download XML
Export Citation
Article outline
Abstract

Other Articles By Authors

Related pages

Tools

Copyright © AIMS Press

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog