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

Yihuan Mao (Institute for Interdisciplinary Information Sciences, Tsinghua University), Yipeng Kang (State Key Laboratory of General Artificial Intelligence, BIGAI), Peilun Li (Shanghai Tree Graph Blockchain Research Institute), Ning Zhang (Washington University in St. Louis), Wei Xu (Institute for Interdisciplinary Information Sciences, Tsinghua University), Chongjie Zhang (Washington University in St. Louis)

Abstract

As AI agents become integral to infrastructure, robust coordination and message synchronization are crucial. The Byzantine Generals Problem (BGP) models resilience in multi-agent systems (MAS) under adversarial conditions, handling scenarios with malicious agents-stemming from AI hallucinations or external attacks. Traditional BGP demands global consensus, which is often unnecessary and inefficient in practice. We introduce Imperfect BGP (IBGP), aligning with the local coordination patterns in MAS to address this gap, offering provable resilience against communication attacks and adaptability to changing environments, as validated by empirical results.