Mean Field Methods for Computer and Communication Systems

Mean Field Methods for Computer and Communication Systems

Mean Field Methods for Computer and Communication Systems Jean-Yves Le Boudec EPFL July 2010 1 Contents Mean Field Interaction Model The Mean Field Limit Convergence to Mean Field The Decoupling Assumption Optimization

2 Mean Field Interaction Model: Common Assumptions Time is discrete or continuous N objects Object n has state Xn(t) (XN1(t), , XNN(t)) is Markov => MN(t) = occupancy measure process is also Markov Objects can be observed only through their state N is large

Called Mean Field Interaction Models in the Performance Evaluation community [McDonald(2007), Benam and Le Boudec(2008)] 3 Intensity I(N) I(N) = expected number of transitions per object per time unit The mean field limit occurs when we re-scale time by I(N) i.e. we consider XN(t/I(N)) In discrete time I(N) = O(1): mean field limit is in discrete time I(N) = O(1/N): mean field limit is in continuous time

4 Example: 2-Step Malware Mobile nodes are either `S Susceptible `D Dormant `A Active Time is discrete Nodes meet pairwise (bluetooth) One interaction per time slot, I(N) = 1/N; mean field limit is an ODE

Possible interactions: 1. Recovery D -> S 2. Mutual upgrade D + D -> A + A 3. Infection by active D + A -> A + A State space is finite = {`S , `A ,`D}

Occupancy measure is M(t) = (S(t), D(t), A(t)) with S(t)+ D(t) + A(t) =1 S(t) = proportion of nodes in state `S [Benam and Le Boudec(2008)] 4. Recovery A -> S 5. Recruitment by Dormant S + D -> D + D Direct infection

S -> D 6. Direct infection S -> A 5 Simulation Runs, N=1000 nodes State = D State = A State = S

Node 1 Node 2 Node 3 D(t) Proportion of nodes In state i=1 A(t) Proportion of nodes In state i=2

6 Sample Runs with N = 1000 7 Example: WiFi Collision Resolution Protocol N nodes, state = retransmission stage k Time is discrete, I(N) = 1/N; mean field limit is an ODE Occupancy measure is M(t) = [M0(t),...,MK(t)]

with Mk(t) = proportion of nodes at stage k [Bordenave et al.(2008)Bordenave, McDonald, and Proutiere, Bordenave et al.(2007)Bordenave, McDonald, and Proutiere] 8 Example: HTTP Metastability N flows between hosts and servers Flow n is OFF or ON Time is discrete, occupancy measure = proportion of ON flows At every time step, every flow switches state with proba matrix that

depends on the proportion of ON flows I(N) = 1; Mean field limit is an iterated map (discrete time) [Baccelli et al.(2004)Baccelli, Lelarge, and McDonald] Other Examples where the mean field limit is in discrete time: TCP flows with a buffer in [Tinnakornsrisuphap and Makowski(2003)] Reputation System in [Le Boudec et al.(2007)Le Boudec, McDonald, and Mundinger] 9 Example: Age of Gossip 10

Example: Age of Gossip Mobile node state = (c, t) c = 1 16 (position) t R R+ (age) Time is continuous, I(N) = 1 Occupancy measure is Fc(z,t) = proportion of nodes that at location c and have age z [Chaintreau et al. (2009)Chaintreau, Le Boudec, and Ristanovic]

11 Extension to a Resource Model can be complexified by adding a global resource R(t) Slow: R(t) is expected to change state at the same rate I(N) as one object Fast: R(t) is change state at the aggregate rate N I(N) -> call it an object of a special class

-> requires special extensions of the theory [Bordenave et al. (2007)Bordenave, McDonald, and Proutiere] [Benam and Le Boudec(2008)] 12 Contents Mean Field Interaction Model The Mean Field Limit

Convergence to Mean Field The Decoupling Assumption Optimization 13 The Mean Field Limit Under very general conditions (given later) the occupancy measure converges, in some sense, to a deterministic process, m(t), called the mean field limit [Graham and Mlard(1994)] consider the

occupancy measure LN in path space 14 Mean Field Limit N = + Stochastic system N = 1000 15

Propagation of Chaos is Equivalent to Convergence to a Deterministic Limit 16 Propagation of Chaos Decoupling Assumption (Propagation of Chaos) If the initial condition (XNn (0))n=1N is exchangeable and there is mean field convergence then the sequence (XNn)n=1N indexed by N is m-chaotic k objects are asymptotically independent with common law equal to the mean field limit, for any fixed k

(Decoupling Assumption) (also called Mean Field Approximation, or Fast Simulation) The law of one object is asymptotically as if all other objects were drawn randomly with replacement from m(t) 17 Example: Propagation of Chaos At any time t Thus for large t : Prob (node n is dormant) 0.3 Prob (node n is active) 0.6 Prob (node n is susceptible) 0.1

18 Example: Decoupling Assumption Let pNj(t|i) be the probability that a node that starts in state i is in state j at time t: pdf of node 2 The decoupling assumptions says that

where p(t|i) is a continuous time, non homogeneous process occupancy measure (t)t)) pdf of node 3 pdf of node 1 19 The Two Interpretations of the Mean Field Limit

m(t) is the approximation for large N of 1. the occupancy measure MN(t) 2. the state probability for one object at time t 20 Contents Mean Field Interaction Model The Mean Field Limit Convergence to Mean Field The Decoupling Assumption Optimization

21 The General Case Convergence to the mean field limit is very often true A general method is known [Sznitman(1991)]: Describe original system as a markov system; make it a martingale problem, using the generator Show that the limiting problem is defined as a martingale problem with unique solution Show that any limit point is solution of the

limitingmartingale problem Find some compactness argument (with weak topology) Never again ! Requires knowing [Ethier and Kurtz(2005)] 22 Kurtzs Theorem Original Sytem is in discrete time and I(N) -> 0; limit is in continuous time

State space for one object is finite 23 Discrete Time, Finite State Space per Object Refinement + simplification, with a fast resource When limit is non continuous: 24 Discrete Time, Enumerable State Space per Object State space is enumerable with discrete topology, perhaps infinite; with a fast resource

Essentially : same as previous plus exchangeability at time 0 25 Discrete Time, Discrete Time Limit Mean field limit is in discrete time 26 Continuous Time Kurtzs theorem also holds in continuous time (finite state space) Graham and Mlard: A generic result for general state space (in particular

non enumerable). 27 Age of Gossip Every taxi has a state Position in area c = 0 16 Age of last received information [Graham and Mlard 1997] applies, i.e. mean field convergence occurs for iid initial conditions [Chaintreau et al.

(2009)Chaintreau, Le Boudec, and Ristanovic] shows more, i.e. weak convergence of initial condition suffices Important for non stationary cases 28 The Bounded Confidence Model Introduced in [Deffuant et al (2000)], used in mobile networks in [Buchegger and Le Boudec 2002]; Proof of convergence to Mean Field in [Gomez, Graham, Le Boudec 2010]

29 PDF of Mean Field Limit 30 Is There Convergence to Mean Field ? Intuitively, yes Discretized version of the problem: Make set of ratings discrete Generic results apply: number of meetings is upper bounded by 2 There is convergence for any initial

condition such that MN(0) -> m0 However, there can be no similar result for the real version of the problem There are some initial conditions such that MN(0) -> m0 while there is not convergence to the mean field There is convergence to mean field if initial condition is iid from m0

This is what matlab does. 31 Contents Mean Field Interaction Model The Mean Field Limit Convergence to Mean Field The Decoupling Assumption Optimization 34

Decoupling Assumption Is true when mean field convergence holds, i.e. almost always It is often used in stationary regime 35 Example In stationary regime: Prob (node n is dormant) 0.3 Prob (node n is active) 0.6 Prob (node n is susceptible) 0.1 Nodes m and n are independent

We are in the good case: the diagram commutes t -> +1 Law of MN(t) N N -> +1 N -> +1 (t)

t -> +1 m* 36 Counter-Example The ODE does not converge to a unique attractor (limit cycle) Assumption H does not hold; does the decoupling assumption still hold ?

Same as before Except for one parameter value h = 0.1 instead of 0.3 37 Decoupling Assumption Does Not Hold Here In Stationary Regime In stationary regime, m(t) = (D(t), A(t), S(t)) follows the limit cycle Assume you are in stationary regime (simulation

has run for a long time) and you observe that one node, say n=1, is in state A It is more likely that m(t) is in region R Therefore, it is more likely that some other node, say n=2, is also in state A R This is synchronization 38 Numerical Example

St)at)ionary point) of ODE Mean of Limit) of N = pdf of one node in st)at)ionary regime pdf of node 2 in st)at)ionary regime, given node 1 is A pdf of node 2 in st)at)ionary regime, given node 1 is D pdf of node 2 in st)at)ionary regime, given node 1 is S

39 Simplified Analysis 2 Decoupling Assumption (Stationary Regime) 1. Recovery 2. Mutual upgrade

3. Infection by active 4. Recovery 5. Recruitment by Dormant

6. Direct infection D -> S D + D -> A + A D + A -> A + A A -> S S + D -> D + D S -> A Solve for (D,A,S)

Has a unique solution 10 Where is the Catch ? Fluid approximation and fast simulation result say that nodes m and n are asymptotically independent But we saw that nodes may not be asymptotically independent is there a contradiction ? 41

The Diagram Does Not Commute For large t and N: where T is the period of the limit cycle Generic Result for Stationary Regime Original system (stochastic): (XN(t)) is Markov, finite, discrete time Assume it is irreducible, thus has a unique stationary proba N Let N be the corresponding stationary distribution for MN(t), i.e. P(MN(t)=(x1,,xI)) = N(x1,,xI) for xi of the form k/n, k integer

Theorem [Benaim] Birkhoff Center: closure of set of points s.t. m R (m) Omega limit: (m) = set of limit points of orbit starting at m 43 Here: Birkhoff center = limit cycle fixed point The theorem says that the stochastic

system for large N is close to the Birkhoff center, i.e. the stationary regime of ODE is a good approximation of the stationary regime of stochastic system 44 Quiz MN(t) is a Markov chain on E={(a, b, c) 0, a + b + c =1, a, b, c multiples of 1/N}

A. MN(t) is periodic, this is why there is a limit cycle for large N. B. For large N, the stationary proba of MN tends to be concentrated on the blue cycle. C. For large N, the stationary proba of MN tends to a Dirac. D. MN(t) is not ergodic, this is why there is a limit cycle for large N.

E (for N = 200) Decoupling Assumption in Stationary Regime Holds under (H) For large N the decoupling assumption holds at any fixed time t It holds in stationary regime under assumption (H) (H) ODE has a unique global stable point to which all trajectories converge Otherwise the decoupling assumption may not hold in stationary regime It has nothing to do with the properties at finite N In our example, for h=0.3 the decoupling assumption holds in stationary regime For h=0.1 it does not

Study the ODE ! 46 Existence and Unicity of a Fixed Point are not Sufficient for Validity of Fixed Point Method Essential assumption is (H) () converges to a unique m* It is not sufficient to find that there is a unique stationary point, i.e. a unique solution to F(m*)=0 Counter Example on figure (XN(t)) is irreducible and thus has a unique

stationary probability N There is a unique stationary point ( = fixed point ) (red cross) F(m*)=0 has a unique solution but it is not a stable equilibrium The fixed point method would say here Prob (node n is dormant) 0.1 Nodes are independent but in reality We have seen that nodes are not independent, but are correlated and synchronized

47 Example: 802.11 with Heterogeneous Nodes [Cho2010] Two classes of nodes with heterogeneous parameters (restransmission probability) Fixed point equation has a unique solution There is a limit cycle 48

Contents Mean Field Interaction Model The Mean Field Limit Convergence to Mean Field The Decoupling Assumption Optimization 49 Decentralized Control Game Theoretic setting; N players, each player has a class, each class has a policy; each player also has a state; Set of states and classes is fixed and finite

Time is discrete; a number of players plays at any point in time. Assume similar scaling assumptions as before. [Tembine et al.(2009)Tembine, Le Boudec, El-Azouzi, and Altman] For large N the game converges to a single player game against a population; 50 Centralized Control [Gast et al.(2010)Gast, Gaujal, and Le Boudec] Markov decision process Finite state space per object, discrete time, N objects

Transition matrix depends on a control policy For large N the system without control converges to mean field Mean field limit ODE driven by a control function Theorem: under similar assumptions as before, the optimal value function of MDP converges to the optimal value of the limiting system The result transforms MDP into fluid optimization, with very different complexity 51 Conclusion

Mean field models are frequent in large scale systems Mean field is much more than a fluid approximation: decoupling assumption / fast simulation Writing the mean field equations is simple and provides a first order approximation Decoupling assumption in stationary regime is not

necessarily true. Mean field equations may reveal emerging properties Control on mean field limit may give new insights 52 References 53 54

[Gomez, Graham, Le Boudec 2010] Gomez-Serrano J., Graham C. and Le Boudec, JY, The Bounded Confidence Model of Opinion Dynamics , preprint, http://infoscience.epfl.ch/record/149416 2 55 56 57

Recently Viewed Presentations

  • Toolbox Strategies for Motivation HELPING OUR ESOL POPULATION

    Toolbox Strategies for Motivation HELPING OUR ESOL POPULATION

    Perseverance . Process . Recognize struggle is an important part of learning . Think about neurons connecting when we struggle or do challenging work . Learn from errors and failures . Do a gallery walk. Write example of time you...
  • Linear Programming Topics  General optimization model  LP model

    Linear Programming Topics General optimization model LP model

    How to solve an LP with the Excel add-in. Linear Programming Topics General optimization model LP model and assumptions Manufacturing example Characteristics of solutions Sensitivity analysis Excel add-ins Product Structure for Manufacturing Example Solution to Manufacturing Example Two-Dimensional Machine Scheduling...
  • Welcome to Kyrene… or welcome BACK to Kyrene

    Welcome to Kyrene… or welcome BACK to Kyrene

    U - Asset videos. X - only folks at your school can access your X: drive. Genesis should be up and running so you can show them Genesis in addition to Parent/Teacher view…how to access it from Genesis.
  • THE SKELETON Objectives To learn and understand 1.

    THE SKELETON Objectives To learn and understand 1.

    THE SKELETON Objectives To learn and understand Functions of the skeleton. Classification of bones. Joints and Movement. Connective Tissue. Types of Movements at Joint
  • The Hydrogen Gas Gun: Part of the Interstellar Roadmap

    The Hydrogen Gas Gun: Part of the Interstellar Roadmap

    At current rocket launch costs of $5,000/lb this is $5 Billion per person! We need to reduce hydrocarbon emissions for large scale space exploration. Conventional Hydrocarbon-LOX rocket motors use finite hydrocarbon resources and produce CO2, while Hydrogen-LOX motors are much...
  • Kinetic Energy and Work; Potential Energy;Conservation of Energy.

    Kinetic Energy and Work; Potential Energy;Conservation of Energy.

    Gravitational force: U= mgh Restoring force of a spring: U =1/2kx2 (KE=1/2mv2) An Example Work has no direction associated with it (it is a scalar). However, work can still be positive or negative. Work done by a force is positive...
  • Computer Networks - SI-35-02

    Computer Networks - SI-35-02

    Slide 5-Elmasri and Navathe, Fundamentals of Database Systems, Fourth Edition Revised by Widodo 2005. Relational Model Concept. First introduced by Dr. E.F. Codd of IBM Research in 1970 in paper titled "Relational Model of Data for Large Shared Data Banks"...
  • CDC Presentation

    CDC Presentation

    Data are based on residence at HIV diagnosis. Data exclude persons whose county of residence is unknown. Rates are per 100,000 population. This slide presents rates (per 100,000 population) of diagnoses of HIV infection among adults and adolescents in 2017,...