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 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 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) .
The speaker was educated at the Indian Institute of Technology, Bombay (B.Tech, 1977), Imperial College, London (MSc, DIC, 1978) and obtained his PhD in Control Theory under A. V. Balakrishnan at UCLA in 1983. He is currently a University Research Chair Professor in the Dept. of ECE at the University of Waterloo, Ont., Canada where he has been since September 2004. Prior to this he was Professor of ECE at Purdue University, West Lafayette, USA. Since 2012 he is a D.J. Gandhi Distinguished Visiting Professor at the Indian Institute of Technology, Bombay, India. He is a Fellow of the IEEE and the Royal Statistical Society. He is a recipient of the INFOCOM 2006 Best Paper Award and was runner-up for the Best Paper Award at INFOCOM 1998. His current research interests are in game theory, applied probability and stochastic analysis with applications to complex networks, network science and wireless systems.