IBGP: Imperfect Byzantine Generals Problem for Zero-Shot Robustness in Communicative Multi-agent Systems

As we move towards the era of AGI, AI agents increasingly integrate into our infrastructure, making their robust coordination and message synchronization vital for ensuring reliable and secure multi-agent interactions. The Byzantine Generals Problem (BGP) is a critical model for constructing resilient multi-agent systems (MAS) under adversarial attacks. It describes a scenario where malicious agents with unknown identities exist in the system-situations that, in our context, could result from LLM agents’ hallucinations or intentional attacks. In BGP, the objective of the entire system is to reach a consensus on the action to be taken. Traditional BGP requires global consensus among all agents; however, in practical scenarios, global consensus is not always necessary and can even be inefficient. Therefore, a refined version of BGP that aligns with the MAS local coordination patterns is needed. We refer to it as Imperfect BGP (IBGP). To tackle this issue, we propose a framework that leverages consensus protocols within general MAS settings, providing provable resilience against communication attacks and adaptability to changing environments, as validated by empirical results. ¹(For a full version of the paper including appendix, please refer to https://arxiv.org/abs/2410.16237.