Boolean Network Models of Collective Dynamics of Open and Closed Large-Scale Multi-agent Systems

This work discusses theoretical models of decentralized large-scale cyber-physical and other types of multi-agent systems (MAS). Arguably, various types of Boolean Networks are among the simplest such models enabling rigorous mathematical and computational analysis of the emerging behavior of such systems and their collective dynamics. This paper investigates determining possible asymptotic dynamics of several classes of Boolean Networks (BNs) such as Discrete Hopfield Networks, Sequential and Synchronous Dynamical Systems, and (finite, Boolean-valued) Cellular Automata. Viewing BNs as an abstraction for a broad variety of decentralized cyber-physical, computational, biological, social and socio-technical systems, similarities and differences between open and closed such systems are rigorously analyzed. Specifically, this paper addresses the problem of enumerating all possible dynamical evolutions of large-scale decentralized cyber-physical, cyber-secure and holonic systems abstracted as Boolean Networks. We establish that, in general, the problem of enumerating possible dynamics is provably computationally hard for both “open” and “closed” variants of BNs, even when all of the following restrictions simultaneously hold: (i) the local behaviors (node update rules) are very simple, monotone Boolean-valued functions; (ii) the network topology is sparse; and (iii) either there is no external environment impact on the system, or the model of the environment is of a rather simple, deterministic nature. Our results provide lower bounds on the complexity of possible behaviors of “real-world” large-scale cyber-physical, socio-technical, social and other distributed systems and infrastructures, with some far-reaching implications insofar as (un)predictability of such systems’ collective dynamics.