Byzantine Fault Tolerance in Distributed Constraint Optimization Problems

Fault tolerance is crucial for the reliability of multi-agent system applications. This paper addresses fault-tolerant algorithms for solving distributed constraint optimization problems (DCOPs) in the presence of Byzantine faults, the most critical type of fault. First, we define a novel class of DCOPs to handle faulty agents, namely a Fault-Tolerant DCOP (FT-DCOP). This class extends the standard DCOP formulation to explicitly introduce the concept of faulty agents. Additionally, weproveanimpossibilityresultforFT-DCOPs regarding the allowable proportion of faulty agents, revealing fundamental limitations. Furthermore, we propose a fault-tolerant algorithm for solving FT-DCOPs that combines the well-known Max-Sum algorithm with replication. Unlike general replication approaches that rely on complex Byzantine consensus protocols and strong assumptions, the proposed algorithm employs a simple verification step based on a synchronous message-passing mechanism and the deterministic nature of Max-Sum, thereby avoiding Byzantine consensus and relaxing the assumptions. Finally, we experimentally evaluate the performance of the standard Max-Sum and the proposed algorithm in the presence of Byzantine faulty agents. The results demonstrate that the standard Max-Sum algorithm is vulnerable to faulty agents and generates low-quality solutions, while the proposed algorithm is resilient and matches the fault-free performance of Max-Sum with manageable communication overhead.

Authors

• Koji Noshiro University of Tsukuba
• Koji Hasebe University of Tsukuba

Keywords

• Distributed Constraint Optimization
• Byzantine Fault Tolerance