Networked Multi-Agent Systems: Coping with Adversarial Agents and Links

Georgetown University, Washington DC

Investigators

Abstract

Networked multi-agent systems consist of a group of participants, referred to as agents,that interact over a network to collectively perform collaborative tasks. Networked multi-agent systems are useful in many application domains, including distributed robotics, sensor networks, and smart grids. Due to their many potential applications, networked multi-agent systems have been a focus of intense research activity over the past several decades. Much of the past work on networked multi-agent systems assumes that the agents, and network links over which they communicate, are both reliable. In practical multi-agent systems, some of the system components may fail or may be compromised by an adversary. Faulty agents may behave incorrectly or in an adversarial manner, and similarly, faulty or compromised network links may deliver messages incorrectly. This project addresses the design and analysis of distributed algorithms for multi-agent systems that are robust to adversarial behavior of agents and links, which may result from failures or attacks. The project focusses on two important classes of problems in multi-agent systems, namely, distributed optimization and distributed hypothesis testing. Robust solutions to these problems may be used to obtain robust solutions to other related problems in multi-agent systems. Thus, the project has the potential to yield solutions that improve robustness of practical multi-agent systems. The project scope includes design of robust algorithms, their theoretical analysis, as well as development of a software tool to evaluate these algorithms. The educational component of the project includes participation of undergraduate and graduate students in project activities, and incorporation of project research outcomes into a related graduate course. The project aims to develop multi-agent algorithms that can tolerate Byzantine failures. The Byzantine fault model captures arbitrary behavior that may be exhibited by faulty or compromised agents or links. A Byzantine faulty agent may be adversarial in nature, and may behave arbitrarily. Possible misbehaviors of a faulty agent include performing computations incorrectly, and sending incorrect or inconsistent messages to other agents. Similarly, a Byzantine faulty link can result in tampering of messages sent over the link. Multi-agent algorithms that can tolerate Byzantine failures are also robust in presence of a wide range of faulty behaviors possible in a practical system. In the context of multi-agent optimization and multi-agent hypothesis testing, the project explores many research challenges, including the following: (i) identifying network properties that are necessary and sufficient to tolerate Byzantine agent or link failures, while achieving desirable properties for the distributed computation, (ii) evaluating the impact of multi-hop forwarding of messages on the multi-agent computation, (iii) mechanisms for network adaptation to improve performance, and (iv) analysis of algorithm behavior in large-scale networks. Through the work on these issues, the project aims to develop fundamental principles that can guide the design of robust fault-tolerant algorithms for different types of distributed computations. The tools used for evaluating the algorithms include mathematical analysis as well as simulation-based experimentation.