Biblio

To observe and control a networked system, especially in failure-prone circumstances, it is imperative that the underlying network structure be 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, remains intact and functions 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 the 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 propose a scheme for a resilient distributed consensus problem through a set of trusted nodes within the network. Currently, algorithms that solve resilient consensus problem demand networks to have high connectivity to overrule the effects of adversaries, or require nodes to have access to some non-local information. In our scheme, we incorporate the notion of trusted nodes to guarantee distributed consensus despite any number of adversarial attacks, even in sparse networks. A subset of nodes, which are more secured against the attacks, constitute a set of trusted nodes. It is shown that the network becomes resilient against any number of attacks whenever the set of trusted nodes form a connected dominating set within the network. We also study a relationship between trusted nodes and the network robustness. Simulations are presented to illustrate and compare our scheme with the existing ones.