Groupe d’études et de recherche en analyse des décisions

Mean field and propagation of chaos in complex interacting

Ravi Mazumdar Department of Electrical and Computer Engineering, University of Waterloo, Canada

Complex interacting system models arise in variety of applications. One of the very well known applications is the case of randomized routing to parallel servers where the criterion is the minimization of latency or blocking. This was studied in the 1990's by Turner (Cambridge), Vvedenskaya and Dobrushin (Moscow), and by Mitzenmacher (Berkeley). While analyzing a finite system is very difficult, the analysis is much simpler when the number of routing choices is large. This leads to the Power of Two rule that states the benefits of the Join the Shortest Queue (JSQ) principle known to be optimal for minimizing the average waiting time in a system with many queues, can be achieved by randomly picking two queues uniformly at random and routing to the shorter queue. What makes this analysis simpler is the role of the mean field.

These problems are re-emerging in the context of cloud resource systems where latency and blocking are important issues. The prior work only addressed the case of identical servers while practical systems can have heterogeneous servers. While this makes the problem much more difficult it also throws up the issue of stability for latency issues and therefore we need to devise more robust and appropriate routing strategies. Only recently have we begun to make progress on analyzing such models. In the talk we will begin with an overview of the classical results and then address the modelling and analysis of heterogeneous systems where we will show that depending on the information available differing strategies can be adopted.

A related group of models are those arising in information ow and consensus problems in social networks. We show that general majority type models on random graphs can be analyzed through mean field techniques that show that impact of heterogeneity on consensus and the time to consensus.

The talk will focus on the mathematical aspects of such models that exploits size in the number of servers and/or users.

Joint work with Arpan Mukhopadhyay (Waterloo), Rahul Roy (Indian Statistical Institute) and A. Karthik (Waterloo).

Entrée gratuite.
Bienvenue à tous!