Resilient Networks for Multi-Agent Systems based on Graph Self-Organization into Random Approximate Regular Graphs

This paper proposes a distributed protocol that can self-organize a connected graph representing a network into a random approximate regular graph with an arbitrary degree, which is known to possess robustness properties against link and node failures, including also DoS network attacks. The scenario under consideration is that of an unstructured peer-to-peer network, where the agents and are allowed to close communications with their neighbors and establish new communications with two-hop neighbor, while the time-varying graph topology remains unknown. To validate the efficacy of the proposed protocol, we examine the spectral properties of the self-organizing graph, and we numerically show that they approach those of random regular graphs, particularly for large networks. We also compare the performance of the proposed protocol with the state-of-the-art, showing improvements in convergence speed and scalability, despite the absence of synchronous multi-node coordination of previous approaches in the literature.