Non-resilience of Resilient Distributed Consensus in Multi-agent Systems
This thesis explores the resilient distributed consensus in networks that lack the necessary structural robustness to achieve consensus in the presence of malicious agents. While exist- ing solutions provide robustness conditions for consensus among normal agents, they fail to evaluate network performance comprehensively when the graph’s robustness is insufficient. To address this limitation, we introduce the concept of non-convergent nodes, representing agents unable to attain consensus with any arbitrary agent due to malicious agents in the network. This notion allows us to classify graphs based on their robustness levels and assess partial performance. This study initially establishes the (r, s)-robustness of commonly en- countered graphs, such as complete, complete bipartite, 1-D distance, and circulant graphs. Our approach facilitates easier identification of robustness and enables us to gain insights into the behavior of non-convergent nodes. By understanding the dynamics of these non- convergent nodes, we can establish more relaxed conditions for converging subgraphs, which are the subgraphs that are guaranteed to converge. This knowledge enhances our under- standing of resilient algorithms and their behavior in practical scenarios. Furthermore, we present graphs with given robustness levels, including (F + 1, 1), (F, F ), and (F + 1, F ) ro- bustness, and determine the maximal number of non-convergent nodes associated with each graph. This quantification of non-resilience sheds light on the impact of graph robustness on the network’s ability to achieve consensus. Surprisingly, we find that graphs with the same structural robustness may exhibit varying degrees of non-resilience, leading to different network performance outcomes. Through numerical evaluations, we demonstrate that our approach provides a comprehensive resilience perspective beyond the conventional binary view of success or failure in the face of malicious agents. By quantifying network perfor- mance under sub-optimal robustness conditions and identifying converging subgraphs, our study opens up new possibilities for designing more resilient consensus algorithms.