The Struggle for Independence
Seminar Room 1, Newton Institute
AbstractNetwork theorists seek accurate, parsimonious stochastic models of large-scale networks. A very useful property for obtaining such models is the statistical independence of the congestion measures at the different nodes of the network. This property allows a large-scale system to be decomposable into probabilistically independent modules, facilitating analysis. The successful Jackson and Kelly network models possess this property. However, modern network systems, such as load balancers, switching fabrics and the Internet, do not possess this property. A new approach is needed.
Using recent ideas from statistical physics, notably the Cavity Method, we describe a framework for analyzing large-scale complex networks. We apply this framework to randomized load balancing systems, generalizing the class of tractable models. A key observation is that, in order to be scalable, modern networks are designed so that the interaction between the components is kept to a minimum, making the components only weakly dependent. Thus, any finite subset of the components become independent as the network size grows without bound. We describe the steps involved in establishing independence and list a few practical consequences.
Joint work with Maury Bramson and Yi Lu