Trust-Based Algorithms for Resilient Multi-Agent Systems

Abstract

Multi-agent systems---ranging from robot teams to computer networks and distributed sensors---are increasingly deployed in real-world settings due to their advantages in scalability, parallelism, cost efficiency, and more. A core enabler of coordination in these systems is information exchange between agents, which can also become their Achilles' heel in the presence of malicious agents. Without any precautions, adversaries can severely degrade system performance simply by sending false data to other agents. Therefore, designing resilient algorithms capable of withstanding adversarial behavior is essential for enabling the safe deployment and widespread adoption of such systems, which is the ultimate goal of this thesis. In this work, we consider settings where agents can leverage stochastic inter-agent trust signals, typically obtained from physical channels of information such as onboard sensors or fingerprints of wireless communication signals commonly available in cyber-physical systems. When used to quantify the trustworthiness of the transmitting agent or its transmitted data, prior work has shown that the availability of such signals can enable strong resilience guarantees---beyond what is achievable through data-based methods alone. Motivated by this potential, we focus on enhancing the resilience of distributed algorithms in multi-agent systems by incorporating inter-agent trust signals. To this end, we pursue three main directions: 1) developing detection and learning algorithms that identify legitimate and malicious agents beyond the applications and settings considered in existing work, 2) designing resilient distributed algorithms that integrate trust to solve fundamental multi-agent problems, including optimization, consensus, and hypothesis testing, and 3) deepening the theoretical understanding of resilience through trust observations by analyzing their limitations and studying how adversarial strategies affect the performance of the resulting algorithms. We begin by addressing the joint challenges posed by directed communication graphs and the presence of adversaries. We develop a learning protocol that enables each agent to estimate the trustworthiness of all other agents in the system, extending prior detection results that were limited to learning about neighboring agents in undirected graphs. Next, we consider both constrained and unconstrained distributed optimization problems over directed graphs in adversarial settings, with a focus on achieving resilience while maintaining fast convergence. We first tackle the challenges introduced by directed graphs and constraint sets alone and propose a new gradient tracking-based algorithm, Projected Push-Pull, which achieves fast convergence under these conditions. We then extend this framework to incorporate adversaries by combining the learning protocol with Projected Push-Pull, resulting in an algorithm that achieves both fast and resilient convergence in the presence of adversarial agents. We investigate the performance of our algorithm in comparison to other resilient trust-based and data-only methods, and demonstrate that it outperforms them in various aspects, including convergence speed and the ability to eliminate the influence of malicious agents, while remaining applicable to a wider range of settings. In the second part of the thesis, we shift our focus to challenges arising from the dynamic behavior of malicious agents, as well as the limitations of trust observations. To study these aspects, we consider the resilient consensus problem, where legitimate agents follow linear consensus updates while adversaries exhibit time-varying attack behavior, varying their probability of attack at each time step rather than attacking persistently as commonly assumed in the literature. We design a detection algorithm that uses a time-varying threshold: each agent first identifies its most trusted neighbors based on trust observations and then uses them as a reference to classify other agents. We characterize the performance of this detection algorithm, with particular attention to how it depends on the frequency of adversarial attacks and the choice of thresholds. Additionally, we analyze how dynamic adversarial behavior impacts consensus, specifically in terms of agents' ability to reach agreement and the deviation from the nominal outcome that would be achieved in the absence of adversaries. Finally, we study two problems that highlight the impact of having a limited number of trust observations from each agent, as well as the influence of adversarial strategies on system performance. In the first problem, we revisit the resilient consensus setting, now considering a finite-horizon scenario where agents execute the consensus protocol for a known, limited number of steps. We model switching adversaries that behave cooperatively until a designated attack time, after which they send misleading data to maximize disagreement among legitimate agents. To address this, we propose a sliding-window-based detection algorithm that accounts for the adversaries’ switching behavior. We show that strong adversaries, who know when they will be detected, can compute their optimal attack strategy in polynomial time, and we provide bounds on the maximum disagreement they can induce among legitimate agents. In the second problem, we study a binary hypothesis testing setting where a Fusion Center (FC) estimates the occurrence of an event after collecting binary measurements from distributed sensors. We consider a one-shot estimation scenario, in which the FC receives only a single measurement and a single trust observation from each sensor before making a decision. To address this, we develop the Adversarial Generalized Likelihood Ratio Test (A-GLRT), a polynomial-time algorithm that jointly estimates each agent’s trustworthiness and the adversarial strategy using both sensor data and trust observations, and then infers the true hypothesis based on these estimates. We deploy A-GLRT in hardware experiments emulating a crowdsensing application, where robots estimate and report traffic conditions on a mock-up road network under a Sybil attack, in which malicious agents spoof fake identities. By leveraging trust observations derived from the uniqueness of wireless signal characteristics, we show that A-GLRT outperforms existing resilient methods and maintains good performance even when malicious agents are in the majority. In all parts of the thesis, we provide rigorous theoretical guarantees for the proposed algorithms, including results on convergence, convergence rates, and probabilistic bounds on detection and classification errors. Moreover, we support these findings with extensive numerical simulations that validate the effectiveness and applicability of our methods.