Computational Analysis of Complex Systems : Discrete Foundations, Algorithms, and the Internet

Abstract

Complex systems are collections of functionally highly interdependent elements. To analyze, control, and manipulate the connection between the behavior of a complex system as a whole and its local behavior on the elementary scale is a central in complex systems research. We investigate a mathematical framework for finite, discrete dynamical systems capable to serve as a reference model for a computational analysis of complex systems from an ex post point of view. The framework is based on clone theory and forbidden graph minors an exhausts the class of all finite systems. Within the framework the islands of tractability for finding and counting fixed points in Boolean dynamical systems can be completely described. The benefits from such complexity classifications are precise maps of where simulations of complex systems allow short cuts. An application representative for theory building is Internet routing using the Border Gateway Protocol (BGP). The dissemination of BGP routes results from a discrete dynamical process without convergence guarantees by the protocol. Rather, the dynamic is driven by local policies of Autonomous Systems according to their business relationships. As business contracts are not publicly available, inferring relationships is an important algorithmic problem for ex post analyses. In respect of thereof, a purely combinatorial approach is presented. Experiments suggest that the involved acyclicity conditions should be an integral part of relationship models.