Abstract
This paper introduces P-RODA, the first privacy-preserving framework for "region-optimal" algorithms in Distributed Constraint Optimization Problems (DCOPs). By combining secret sharing and homomorphic encryption, P-RODA allows groups of agents to coordinate and find high-quality solutions without revealing their private constraints or internal decision-making logic to a central mediator. Experimental results demonstrate that the framework is highly scalable, with computational overhead remaining independent of the total number of agents in the network.
Introduction
In multi-agent systems such as smart grids or sensor networks, agents must coordinate to minimize a global cost function, a task modeled as a Distributed Constraint Optimization Problem (DCOP). While complete algorithms guarantee optimal solutions, they often suffer from poor scalability in large-scale systems. Conversely, local search algorithms are fast but lack quality guarantees.
Region-optimal algorithms offer a middle ground, guaranteeing the best solution within a specific "region" (a group of $k$ agents within distance $t$). However, these algorithms typically rely on a central mediator to collect data from the group, leading to significant privacy risks where private cost functions and agent states are exposed. This work addresses the challenge of achieving the quality guarantees of region-optimality without sacrificing agent privacy.
Methodology
The authors propose P-RODA (Private Region Optimal DCOP Algorithm), a framework that "hardens" the generalized RODA framework using two primary cryptographic pillars:
- Homomorphic Encryption (Paillier Cryptosystem): This allows agents to perform additions on encrypted data. In P-RODA, agents encrypt their local cost tables (tensors). A "deputy" agent aggregates these encrypted tables, and a mediator decrypts the result to identify the optimal assignment index without ever accessing raw cost values. Benchmarks show encryption takes ~2ms and decryption ~3ms per operation.
- Secret Sharing: To determine which group provides the greatest improvement in a competition phase, P-RODA splits improvement values into random pieces distributed among agents. This ensures that no single agent knows the exact magnitude of another group's improvement.
To further protect privacy, tasks are split between a mediator (holding the decryption key) and a deputy (handling encrypted aggregation and permutation), ensuring neither party has enough information to reconstruct private data.
Experimental Evaluation
The performance of P-RODA was evaluated using synthetic DCOP benchmarks across three network topologies: Random (Erdős-Rényi), Scale-free (Barabási-Albert), and Small-world (Watts-Strogatz).
Scalability and Network Size
A major insight from the evaluation is that the computational overhead of P-RODA is decoupled from the total number of agents ($n$). As shown in the figure below, the overhead remains nearly constant as the network size increases from 100 to 1000 agents for random and small-world topologies. Scale-free networks exhibit slightly higher overhead due to the presence of highly connected "hubs" that increase local neighborhood sizes.
Impact of Group Size
While P-RODA scales well with network size, it faces complexity challenges as the group size ($k$) increases. Because the size of cost tensors grows as $d^k$ (where $d$ is the domain size), the computational overhead increases exponentially with $k$. The following figure illustrates this growth, showing that overhead is minimal for small $k$ but grows rapidly beyond $k=6$.
Conclusion
P-RODA successfully simulates the non-private RODA framework, inheriting its convergence and quality guarantees while providing robust privacy protections for semi-honest agents. While the exponential growth relative to group size presents a computational limit for large $k$, the algorithm's independence from total network size makes it a powerful tool for large-scale distributed coordination. Future work will focus on achieving full decision privacy and hardening assignment privacy against information leakage between direct neighbors.
Summary updated