r-Robustness and (r,s)-Robustness of Circulant Graphs
For researchers designing networks for resilient consensus algorithms, this work offers a scalable directed graph class with analytically determined robustness, addressing a gap in existing methods that mostly focus on undirected graphs.
The paper identifies a class of scalable directed circulant graphs whose robustness (r- and (r,s)-robustness) is determined by a single parameter k, providing a method to construct graphs with guaranteed robustness levels for consensus algorithms in the presence of misbehaving agents. The results are supported by computer simulations.
There has been recent growing interest in graph theoretical properties known as r- and (r,s)-robustness. These properties serve as sufficient conditions guaranteeing the success of certain consensus algorithms in networks with misbehaving agents present. Due to the complexity of determining the robustness for an arbitrary graph, several methods have previously been proposed for identifying the robustness of specific classes of graphs or constructing graphs with specified robustness levels. The majority of such approaches have focused on undirected graphs. In this paper we identify a class of scalable directed graphs whose edge set is determined by a parameter k and prove that the robustness of these graphs is also determined by k. We support our results through computer simulations.