AFOSR: Global Behavior in Large Scale Systems (project start date – June 1st, 2010)

Abstract. We consider fusion of information collected by a large scale, distributed, sparsely connected network of sensing agents, sensing centers, or sensors monitoring a large collection of dynamical (possibly stochastic) sparsely coupled systems. Examples include large critical infrastructures such as the power grid, the telecom wireless infrastructure, or an information network. We develop new methodologies to study the global behavior of these large scale networked systems that emerges from a multitude of local actions (events) and to study fusion (e.g., detection, estimation) under their prevailing operation conditions, e.g., besides measurement and communication noise, the intermittency of infrastructure failures. There are a number of challenges: 1) the large scale of the system makes it not practical to have complete model descriptions that account with minutiae for all the local (component) dynamics as well as for their complex interactions; 2) these systems are subject to rare but catastrophic events, like a continental size blackout, a system wide attack that spirals up to overpower the system resources, or service delays that cascade out of control; 3) often, large scale networked systems exhibit a phase change, i.e., below critical values of a set of parameters, the system is well behaved, while above these critical values the system becomes unstable or collapses; and finally, 4) the amount of data potentially collected over time and from all the monitoring centers may be staggering, making it unfeasible to process centrally at a fusion center. We develop methods that can handle many of these challenges. Our approach emphasizes the‘largeness’ of the system and focus on asymptotic behavior. Surprisingly, it allows understanding the global behavior that emerges from the many local interactions and design strategies for appropriate provisioning of resources to avoid or prevent out of control undesirable behaviors.We capture these questions in the context of stochastic networks and their limiting behavior, e.g., obtained by studying their fluid limit and large deviation principle. We model the large scale system by a network of dynamic nodes and abstract from the physics of the system the events of interest (unserviced calls, or system attacks). We model the local requests or events as point processes, their propagation across the network by rate parameters, and the state of the system by a jump Markov process. To study the system behavior, we focus on a global entity, the empirical distribution of the state. To study the emergent system behavior, we consider normalized versions of the system under appropriate scalings. This approach allows addressing different questions–e.g., switching among different stability regions, (multistability), occurrence of phase change behavior, or rate at which catastrophic behavior emerges. To process the data, we study distributed inference under appropriate system conditions, like system failures. Our work develops models, analysis methodologies, and signal and information processing techniques that are needed to address global issues regarding large scale networked systems. Beyond moment (mean or second order) analysis, it focus on sample path behavior and large deviation principle to determine rates at which rare, but catastrophic, behaviors occur. These methods, not yet commonly used by researchers in these areas, are the appropriate tools to handle the large scale of these systems. The foundational nature of our work applies across a number of systems including the power grid, telecom wireless networks, or cyber-security infrastructures, e.g., botnets of compromised computers. We propose to characterize the rate at which rare, but catastrophic, events occur, so operators can provision the system (e.g., installed capacity) so that these rates are well within the safety guarantees adopted by the decision or policy makers. Our work will lead to better understanding of how to fuse the distributed information collected from a large scale system to infer their global behaviors.

Lab Members

1. Augusto Santos
2. Joya Deri