Distributed Averaging Under Constraints on Information Exchange: Emergence of Lévy Flights

In this paper, we study the fragility of a popular distributed averaging algorithm when the information exchange among the nodes is limited by communication delays, fading connections and additive noise. We show that the otherwise well studied and benign multi-agent system can generate a collective global complex behavior. We characterize this behavior, common to many natural and human-made interconnected systems, as a collective hyper-jump diffusion process and as a Lévy flight process in a special case. We further describe the mechanism for its emergence and predict its occurrence, under standard assumptions, by checking the Mean Square instability of a certain part of the system. We show that the strong connectivity property of the network topology guarantees that the complex behavior is global and manifested by all the agents in the network, even though the source of uncertainty is localized. This work is the first, to the best of our knowledge, to establish the intimate relationship between the propagation of channel uncertainties in networked systems, the MS stability robustness and the emergence of Lévy flights in distributed averaging systems. As averaging is central to science and engineering, the results of the paper may have far-reaching consequences on the understanding and engineering of complex networked systems.