2018/10/01 by James Usevitch, Dimitra Panagou, Usevitch, James +1
Computer Science · #Distributed Control Multi-Agent Systems #Distributed systems and fault tolerance #FOS: Computer and information sciences #FOS: Electrical engineering #Multiagent Systems (cs.MA) #Optimization and Search Problems #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1810.01784
openalex publication_date 2018/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Convergence guarantees of many resilient consensus algorithms are based on\nthe graph theoretic properties of r- and (r,s)-robustness. These algorithms\nguarantee consensus of normally behaving agents in the presence of a bounded\nnumber of arbitrarily misbehaving agents if the values of the integers r and\ns are sufficiently high. However, determining the largest integer r for\nwhich an arbitrary digraph is r-robust is highly nontrivial. This paper\nintroduces a novel method for calculating this value using mixed integer linear\nprogramming. The method only requires knowledge of the graph Laplacian matrix,\nand can be formulated with affine objective and constraints, except for the\ninteger constraint. Integer programming methods such as branch-and-bound can\nallow both lower and upper bounds on r to be iteratively tightened.\nSimulations suggest the proposed method demonstrates greater efficiency than\nprior algorithms.\n