To observe and control a networked system, especially in failure-prone circumstances, it is imperative that the underlying network structure is robust against node or link failures. A common approach for increasing network robustness is redundancy: deploying additional nodes and establishing new links between nodes, which could be prohibitively expensive. This paper addresses the problem of improving structural robustness of networks without adding extra links. The main idea is to ensure that a small subset of nodes, referred to as the trusted nodes, remain intact and function correctly at all times. We extend two fundamental metrics of structural robustness with the notion of trusted nodes, network connectivity and $r$-robustness, and then show that by controlling the number and location of trusted nodes, any desired connectivity and robustness can be achieved without adding extra links. We study complexity of finding trusted nodes and construction of robust networks with trusted nodes. Finally, we present a resilient consensus algorithm with trusted nodes and show that, unlike existing algorithms, resilient consensus is possible in sparse networks containing few trusted nodes.

In this paper, we study resilient distributed diffusion for multi-task estimation in the presence of adversaries where networked agents must estimate distinct but correlated states of interest by processing streaming data. We show that in general diffusion strategies are not resilient to malicious agents that do not adhere to the diffusion-based information processing rules. In particular, by exploiting the adaptive weights used for diffusing information, we develop time-dependent attack models that drive normal agents to converge to states selected by the attacker. We show that an attacker that has complete knowledge of the system can always drive its targeted agents to its desired estimates. Moreover, an attacker that does not have complete knowledge of the system including streaming data of targeted agents or the parameters they use in diffusion algorithms, can still be successful in deploying an attack by approximating the needed information. The attack models can be used for both stationary and non-stationary state estimation. In addition, we present and analyze a resilient distributed diffusion algorithm that is resilient to any data falsification attack in which the number of compromised agents in the local neighborhood of a normal agent is bounded. The proposed algorithm guarantees that all normal agents converge to their true target states if appropriate parameters are selected. We also analyze trade-off between the resilience of distributed diffusion and its performance in terms of steady-state mean-square-deviation (MSD) from the correct estimates. Finally, we evaluate the proposed attack models and resilient distributed diffusion algorithm using stationary and non-stationary multi-target localization.

Distributed machine learning algorithms are increasingly used in multirobot systems and are prone to Byzantine attacks. In this article, we consider a distributed implementation of the stochastic gradient descent (SGD) algorithm in a cooperative network, where networked agents optimize a global loss function using SGD on the local data and aggregation of the estimates of immediate neighbors. Byzantine agents can send arbitrary estimates to their neighbors, which may disrupt the convergence of normal agents to the optimum state. We show that if every normal agent combines its neighbors’ estimates (states) such that the aggregated state is in the convex hull of its normal neighbors’ states, then the resilient convergence is guaranteed. To assure this sufficient condition, we propose a resilient aggregation rule based on the notion of centerpoint, which is a generalization of the median in the higher-dimensional Euclidean space. We evaluate our results using examples of target pursuit and pattern recognition in multirobot systems. The evaluation results demonstrate that distributed learning with average, coordinate-wise median, and geometric median-based aggregation rules fail to converge to the optimum state, whereas the centerpoint-based aggregation rule is resilient in the same scenario.

In this paper, we demonstrate that there is a conflicting relation between two crucial properties—controllability and robustness—in linear dynamical networks of diffusively coupled agents. In particular, for any given number of nodes N and diameter D, we identify networks that are maximally robust using the notion of Kirchhoff index and then analyze their strong structural controllability by computing the minimum number of leaders (nodes receiving external control inputs) needed to make such networks controllable under all feasible coupling weights. Then, for any N and D, we obtain a sharp upper bound on the minimum number of leaders needed to design strong structurally controllable networks with N nodes and diameter D. We also discuss that the bound is best possible for arbitrary values of N and D. Moreover, we construct a family of graphs for any N and D such that the graphs have maximal edge sets while being strong structurally controllable with a number of leaders in the proposed bound. We then analyze the robustness of this graph family. The results suggest that optimizing robustness increases the number of leaders needed for strong structural controllability.