Biblio

We consider a graph property known as r-robustness of the random K-out graphs. Random K-out graphs, denoted as \$\textbackslashtextbackslashmathbbH(n;K)\$, are constructed as follows. Each of the n nodes select K distinct nodes uniformly at random, and then an edge is formed between these nodes. The orientation of the edges is ignored, resulting in an undirected graph. Random K-out graphs have been used in many applications including random (pairwise) key predistribution in wireless sensor networks, anonymous message routing in crypto-currency networks, and differentially-private federated averaging. r-robustness is an important metric in many applications where robustness of networks to disruptions is of practical interest, and r-robustness is especially useful in analyzing consensus dynamics. It was previously shown that consensus can be reached in an r-robust network for sufficiently large r even in the presence of some adversarial nodes. r-robustness is also useful for resilience against adversarial attacks or node failures since it is a stronger property than r-connectivity and thus can provide guarantees on the connectivity of the graph when up to r – 1 nodes in the graph are removed. In this paper, we provide a set of conditions for Kn and n that ensure, with high probability (whp), the r-robustness of the random K-out graph.

We show that competitive engagements within the agents of a network can result in resilience in consensus dynamics with respect to the presence of an adversary. We first show that interconnections with an adversary, with linear dynamics, can make the consensus dynamics diverge, or drive its evolution to a state different from the average.We then introduce a second network, interconnected with the original network via an engagement topology. This network has no information about the adversary and each agent in it has only access to partial information about the state of the other network. We introduce a dynamics on the coupled network which corresponds to a saddle-point dynamics of a certain zero-sum game and is distributed over each network, as well as the engagement topology. We show that, by appropriately choosing a design parameter corresponding to the competition between these two networks, the coupled dynamics can be made resilient with respect to the presence of the adversary.Our technical approach combines notions of graph theory and stable perturbations of nonsymmetric matrices.We demonstrate our results on an example of kinematic-based flocking in presence of an adversary.