Byzantine Resilient Consensus, Learning, and Optimization in Distributed Multi-Agent Systems
With the ever-growing technological explosion of the world, distributed systems are becoming more and more widespread and spawning numerous applications in multi-agent systems including sensor networks, cloud computing, swarm robotics, and intelligent systems. Distributed consensus, learning, and optimization algorithms play an important role in such distributed multi-agent systems. However, these algorithms are vulnerable to cyber-attacks. In particular, a single adversarial agent exchanging malicious information with normal agents may ruin the integrity of the entire network. This work proposes multiple solutions to address the vulnerabilities of such distributed algorithms and provides guarantees for the resilient operation in multi-agent systems. Throughout the thesis, we study the resilient vector consensus problem and propose a centerpoint-based consensus method that generalizes the resilience property of the median into higher dimensions, which offers more advantages in terms of computational complexity and characterization than the existing methods. We extend this consensus method into distributed learning and optimization problems, particularly for robotic applications, where the position vector is in two or three dimensions, and a centerpoint can be computed efficiently in O(n) and O(n^2) time complexity. For high-dimensional distributed learning problems, we incorporate the idea of optimizing the objective function in designing the cooperation strategy, which is both efficient and guarantees the resilient cooperation among normal agents to an arbitrary number of adversarial agents, without the need of a tailored upper-bound of the adversaries. Further, we apply such an approach into distributed multi-task learning, clustering, and reinforcement learning problems. Our results are supported by theoretical results and well validated by numerical implementations and practical experiments. We hope our results could assist people in the design and implementation of real-world applications in distributed multi-agent systems.