Complexity and fragility with applications to Internet technology

Many complex networks are “robust yet fragile” (RYF), exhibiting remarkable robustness of their basic functionality despite large perturbations in their environments and component parts, yet also extreme fragility to cascading failure events triggered by relatively small perturbations. Cancer, infectious diseases of humans, animals, plants, and computer networks, auto-immunity, power outages, market crashes, denial-of-service attacks, terrorist hijackings, etc., are familiar examples of fragilities in complex systems. The entire scientific enterprise of experimentation, modeling, and simulation of complex systems has been most successful at studying their typical or generic behaviors, but our experience of RYF systems in the real world may be dominated by extremely rare events. While there are areas of engineering that deal effectively with RYF systems, they are currently more isolated and fragmented within narrow technical disciplines than is desirable.

This talk will describe efforts to develop rigorous, systematic, and general methods to study RYF systems, including a deep understanding of the intrinsic sources of RYF. Complexity introduced to provide robustness for some perturbations inevitable creates fragilities elsewhere, which can lead to a “complexity-fragility” spiral. Scalable inference algorithms will be developed to overcome the apparent intractability of robustness analysis of models exhibiting RYF. Analysis of RYF systems using standard discrete-event or continuous simulation methodologies alone is inadequate because the systems can be enormous, and simulation time for even simple models to get statistical significance can be prohibitive. Thus both multiscale models and robustness analysis tools that avoid wasting time in simulation of benign scenarios are essential. Interaction with data also has major challenges, typified by two extreme scenarios. In one, methods of reasoning from sparse data about scenarios as yet untested is needed, to both suggest targeted testing, but also to predict rare events that may not be experimentally accessible. At the other extreme, there can be overwhelming floods of data from which signatures of anomalous events must be detected.

Automating and computationally augmenting scientific and mathematical inference from noisy and incomplete data for uncertain models has long been an elusive goal, but is necessary for the study of RYF. Essentially all computational problems for detailed models in these domains are apparently intractable, such as finding worst-case behavior in a model, verifying the robustness of protocols, or proving that some proposed model cannot explain observed data. Thus the asymmetry between NP (where proofs are always short, though search may be intractable) and coNP (where short proofs may not exist) is as significant as the more familiar one between P (both search and proof are easy) and NP. A key enabling insight is that “complexity implies fragility” or more precisely “dual complexity implies primal fragility.” Through a combination of mathematics from control theory, dynamical systems, real algebraic geometry, and operator theory, computational complexity can be directly connected with problem fragility in such a way as to render robustness analysis and verification tractable.

A broad range of networks from many disciplines exhibit RYF features, including terrestrial and aquatic ecosystems, the dynamics and impact of forest fires, earthquakes, and other natural disasters. A main motivation is from technological networks, but particularly those involving ubiquitously embedded computer networks, and future scenarios in which such networks control critical infrastructure. Here there is tremendous potential for both efficient and robust nominal operations and catastrophic cascading failure events, both from malfunction and attack. The Internet itself, though familiar and well-understood informally, still lacks a coherent theoretical foundation. The aim in these diverse studies is to identify the common structures contributing to the RYF behavior, and develop both simple explanatory and detailed predictive models with associated analysis tools. The preliminary progress already made is striking and has been applied to understanding, for example, the robustness of complex control systems, the performance of internet protocols, the dynamics of forest fires, and bacterial chemotaxis and stress response. One signature of RYF systems is power law statistics in event sizes. Power laws are ubiquitous in natural and human systems, and are heavily studied, yet remain a source of tremendous confusion and specious theorizing in the scientific literature. A major aim of this work is to resolve this confusion and broadly educate scientists, engineers, and the public about the relevance and rigorous treatment of power law statistics.

Presenter(s)

John Doyle received his PhD in Mathematics from UC Berkeley in 1984, and has been a Professor at Caltech since 1986, where he is in the departments of Electrical Engineering, BioEngineering, and Control and Dynamical Systems. His current research interests are in theoretical foundations for complex networks in engineering and biology, as well as multiscale physics and financial markets, focusing on the interplay between robustness, feedback, control, dynamical systems, computation, communications, and statistical physics. The current application domains include Internet protocols with provably robust theoretical features; theory and software to support post-genomics research in complex biological networks; and new theoretical tools for the study of nonequilibrium statistical physics, turbulence, and quantum measurement and control.

John Doyle's early work was in the mathematics of robust optimal control. He is the author of several books and of some of the most widely used control software toolboxes for high performance commercial and military aerospace systems, including Space Radiometer, F-16, Shuttle Orbiter, electric power generation, distillation, catalytic reactors, active suspension, and CD players. He has received almost every major prize in control theory there is, including the IEEE Baker (also ranked in the top 10 ``most important'' papers world-wide in pure and applied mathematics from 1981-1993), the IEEE AC Transactions Axelby, and IEEE Control Systems Field Award. Interestingly, he has also held national and world records and championships in various sports.