User Tools

Site Tools


Mean Field and Propagation of Chaos in Complex Interacting Systems

Ravi Mazumdar, University Research Chair Professor, 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. 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 {\em 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 is an important issue. 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 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 flow 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 different types of consensus can take place depending on the majority rule and initial distributions.

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 and A. Karthik .

mean_field_and_propagation_of_chaos_in_complex_interacting_systems.txt · Last modified: 2016/09/01 19:15 (external edit)