کاهش رفتار پیچیده بر سیستم های شبکه ای: تجزیه و تحلیل ساختارهای فضایی ثابت

In this paper, we consider a simple distributed averaging system, which incorporates various communication constraints including delays, noise, and link failures. It has been shown in Wang and Elia (2012) that such networked system generates a collective Lévy flight behavior when part of the system loses mean square (MS) stability. We focus on spatially invariant architectures to gain more insights into how model parameters affect emergence of this complex scale-invariant behavior, and to seek structures robust to communication constraints. Specifically, we develop a computational expression for checking MS stability, which is scalable with the number of unreliable links. We derive the closed form formulas from this expression in the limiting case of zero and large delays, and in the case of large number of nodes. In the limit of large delays, we derive various results that are independent of the network size and its specific interconnections. We find that small inter-agent coupling improves the robustness of the system. Networks with larger connectivity tend to be more fragile in the presence of fading connections for fixed inter-agent coupling. That gossiping improves the robustness and that the lattice is the most robust among the spatially invariant systems with generalized circulant interconnections.

In recent years, there has been much research effort toward the analysis and design of distributed averaging algorithms due to their vast application areas, which include but not limited to estimation over sensor networks (Olfati-Saber, 2007 and Xiao et al., 2005), parallel and distributed computing (Tsitsiklis, 1984), oscillator synchronization (Jadbabaie, Motee, & Barahona, 2005), multi-agent coordination (Fax and Murray, 2004 and Olfati-Saber and Murray, 2004), distributed optimization (Nedic and Ozdaglar, 2009 and Wang and Elia, 2010b). On the other hand, much research interest in scientific disciplines, ranging from statistical physics to system biology, has been attracted to investigate scale-invariant phenomena, phenomena that exhibit power law distributions in interconnected systems; see, e.g., Brockmann, Hufnagel, and Geisel (2006), Mandelbrot (1963) and Mantegna and Stanley (1995). Recently, Wang and Elia (2012) has bridged the gap between these two research areas by showing that a popular distributed averaging system can exhibit a collective Lévy flight behavior, when information exchange between neighboring agents is unreliable and noisy. Lévy flight is a special type of random walk in which the step increments follow a power law distribution with unbounded second moment. Such complex behavior corresponds to large intermittent fluctuation phenomena and has been observed in many natural as well as human-made systems, e.g., human travel patterns (Brockmann et al., 2006), the variation of economic data (Mandelbrot, 1963 and Mantegna and Stanley, 1995), and search patterns of biological systems (Reynolds et al., 2007) to cite a few. Using tools from systems theory and stochastic processes, Wang and Elia (2012) have shown that the loss of Mean Square stability of a part of the system leads to the emergence of the complex behavior in distributed averaging systems over unreliable and noisy networks. In general, the computational cost to check MS (in)stability does not scale with the size of the problem, and this may lead to the difficulty of predicting emergence of the fluctuation behavior. These considerations motivate us to seek special system structures for which the MS stability condition is easier to compute. Studying such structures provides better insights into the limitations and robustness of networked systems, and leads to better management and mitigation strategies of the collective behavior.2 In this paper, we focus our investigation on spatially invariant systems. We show that checking the MS (in)stability condition is simpler for these structures and provide a scalable expression with respect to the number of unreliable links. We further derive closed-form formulas in the cases of zero and large communication delays and in the limit of large number of agents. The formulas quantify how the network structure (topology), the Quality of Service (QoS) of the network and the inter-agent coupling affects the MS stability property of the system. In systems theory, large delays are usually difficult to handle especially by the state-space approach as they directly affect the dimension of the system. An important contribution of this paper is in providing a simple analytic expression for the MS stability test in the limit of large delays. Our approach exploits the problem structure and employs generating functions of Legendre polynomials to treat the limiting infinite-dimensional system, which is a good approximation of the case of large delays. Moreover, we derive upper and lower bounds to the MS stability formula in case of large delays, which are independent from the number of agents and the specific network topology. These bounds allow us to derive generic conclusions regarding the robustness/fragility of certain interconnection structures which are mostly independent from the fading distribution. In particular, we show that the lattice is the most robust structure among spatially invariant networks with generalized circulant adjacency matrices when the agents do not use the information about the size of their neighborhood. That networks of larger connectivity tend to be more fragile in the presence of fading connections unless the agents can adapt their gains to the size of their neighborhood. For Bernoulli fading, which models simple packet-drop networks, we show that gossiping, or poor QoS, has stabilizing effects at the expense of convergence speed. Moreover, an inter-agent coupling value larger than one always leads to MS instability in the limit of large delays, independent from the interconnection structure and the size of the system. A key distinctive feature of this paper with respect to the existing literature, is that we focus on the fragility induced on the system by the communication constraints and characterized by the MS instability of a part of the system, instead of its convergence properties under different time-varying or stochastic setups, e.g. Patterson and Bamieh (2008), Patterson, Bamieh, and El Abbadi (2010), Huang, Dey, Nair, and Manton (2010), Huang and Manton (2010), Kar and Moura (2009), Tahbaz Salehi and Jadbabaie (2008) and Xiao, Boyd, and Kim (2007). This view was first proposed in Elia (2006), which studied the effect of MS instability on spatially-invariant networked systems, using the approach of Elia (2005), and further developed in Wang and Elia (2012). Besides the focus on the emergence and characterization of complex behavior, we provide MS stability analysis in more general settings. Patterson et al. (2010) considers the MS stable regime of a spatially invariant distributed averaging systems, mostly focuses on a undirected d-torus network, and studies the convergence rate for small probability of packet drops. Patterson and Bamieh (2008), like this paper, applies the methodology of Elia (2006) to a distributed averaging algorithm but again with symmetric link failures on undirected circulant graphs. Instead, we consider more general directed circulant graphs with general IID fading, adopt a frequency domain approach to derive a quantitative analysis in the limit of large delays, and provide a complete characterization and computation of the MS stability test for any packet-drop probability, as well as other fading distributions. Moreover, our analysis shows that the average state cannot display the complex behavior in the averaging system with undirected symmetric switching. Thus, an important aspect of the emergence of complex behavior have been missed in the distributed averaging literature where the symmetric switching model has been predominant. Huang et al. (2010), Huang and Manton (2010) and Kar and Moura (2009) consider algorithms that use time-varying diminishing update gains. This makes the systems well behaved as the unreliable information from the channels is eventually disregarded. In our setup, the update gain is constant over time. Thus, the uncertainty in the communication always acts on the system. This leads to the existence of a critical threshold where part of the system transition from MS stability to MS instability, which characterizes the emergence of Lévy flights. The paper is organized as follows. In Section 2, we provide some background on graph theory and circulant matrices that will be used throughout this paper. In Section 3 we introduce the system model we use in the paper. In Section 4 we present a simulation example that shows the system can be hypersensitive to noise and produce a new emergent collective behavior under certain conditions. In Section 5, we summarize the results of Wang and Elia (2012) which motivated the study in this paper. In Section 6, we focus on spatially invariant systems to find simpler structures and insights on the fragility of the distributed consensus algorithm. We derive closed-form finite-dimensional formulas for the MS stability test in the case of zero and in the limit of large delays. In Section 7, we present network topology independent results on fragility analysis of the algorithm in the case of large delays. Finally, is Section 8, we present the conclusion and future research directions.

In this paper, we have analyzed a popular distributed averaging system under communication uncertainties. We have provided the analysis of MS stability for spatially invariant systems, as this determines the emergence of collective complex behavior characterized in recent work. Specifically, we have provided computational formulas to analyze and evaluate the robustness of different network topologies. We have derived a closed form formula valid in the limiting case of large delays and derived results and limitations that are independent from the specific network topology and only depend on the in degree of the network. In particular, we have found that scaling the coupling between agents according to the number of their neighbors can ensures MS stability. If agents does not have the information about local connection, MS stability will be lost before the loss of mean stability as more neighbors are added. This could have implications for natural networked systems. If the agents do not know how many neighbors they connect to, or are going to connect to, and use a gain above a certain threshold, they are bounded to exhibit complex heavy-tailed evolutions. This is perhaps a reason why such complex behaviors are abundant in nature. These conclusions complement those in Elia (2005) to point out that spatially invariant networks with large number of neighbors tend to be fragile. We have also shown that packet-drop networks with large number of neighbors become more robust by reducing the quality of service of the channels. This is related to silencing techniques and to the stability properties of gossip algorithms. We believe the derivations presented in the paper will extend to more general spatial invariant systems as well as the analysis of other networked systems. We leave this extension to future investigations.