Dual-Domain Defenses for Byzantine-Resilient Decentralized Resource Allocation

Runhua Wang, Qing Ling, Zhi Tian

TL;DR

This paper introduces a new class of decentralized resource allocation algorithms designed to withstand "Byzantine" attacks—where malicious nodes send deceptive data to sabotage the network. By shifting the defense mechanism to the dual domain (filtering the "shadow prices" or Lagrange multipliers rather than the resource allocations themselves), the authors achieve better convergence, simpler updates, and superior consensus compared to existing primal-domain defenses.

What Problem Does This Paper Address?

Decentralized Resource Allocation (DRA) is a cornerstone of modern infrastructure, used in everything from balancing power loads in smart grids to managing traffic in autonomous vehicle networks. In these systems, agents must cooperate to minimize their individual costs while satisfying a global resource constraint (e.g., total power generated must equal total demand).

The "Achilles' heel" of these systems is the Byzantine agent: a node that is either faulty or malicious. These agents don't follow the rules; they can send carefully crafted, misleading messages to their neighbors to prevent the network from reaching an optimal state. While defenses exist for general decentralized optimization, DRA is unique because honest agents are expected to reach different solutions (different resource levels), making standard "consensus-based" filtering of primal variables (the allocations) ineffective.

Methods

The authors propose a primal-dual algorithmic framework augmented with dual-domain defenses.

  1. Primal-Dual Framework: Each honest agent maintains a local primal variable (their resource allocation) and a local dual variable (representing the "shadow price" of the resource).
  2. Dual-Domain Filtering: Instead of trying to filter the primal variables—which naturally vary between nodes—the algorithm filters the dual variables received from neighbors. Since all honest nodes should eventually agree on the "price" of the resource to satisfy the global constraint, the dual domain is the perfect place to enforce consensus.
  3. Robust Aggregation Rules (AGGi): The paper evaluates three specific filtering techniques to "clean" the incoming dual variables:
  4. Coordinate-wise Trimmed Mean (CTM): Discards the $b$ largest and $b$ smallest values before averaging.
  5. Iterative Outlier Scissor (IOS): Repeatedly removes the values furthest from the current mean.
  6. Self-Centered Clipping (SCC): Clips neighbor values so they don't stray too far from the agent's own local value.

The authors provide a rigorous theoretical proof showing that if these rules meet certain "contraction" criteria, the honest agents will converge to a neighborhood of the true optimal solution.

Datasets

The researchers validated their approach using two main setups:

  • Synthetic Quadratic Problem: A network of 100 agents with randomly generated quadratic cost functions and a connected topology. This allowed for controlled testing against various attack types (large-value, small-value, and Gaussian noise attacks).
  • IEEE 118-Bus Test System: A standard benchmark for power system engineering. They simulated an "Economic Dispatch" problem involving 54 generators to demonstrate the algorithm's practical utility in a realistic energy grid scenario.

Key Insights and Ideas

  • The "Consensus" Realization: In DRA, primal variables (allocations) shouldn't be the same across nodes, but dual variables (prices) should be. Filtering the dual domain allows the network to reach a "consensual price" even under attack, which naturally leads to the correct global resource balance.
  • Simplicity is a Feature: Previous state-of-the-art defenses like BREDA require nodes to track extra "auxiliary" variables to monitor their neighbors. This new dual-domain approach eliminates that overhead, leading to simpler updates and lower communication costs.
  • IOS Wins the Day: In numerical tests, the Iterative Outlier Scissor (IOS) rule consistently outperformed CTM and SCC, providing the tightest convergence and best resilience to sophisticated Gaussian attacks.

Key Results

  • Failure of Standard Methods: Attack-free algorithms (like standard decentralized gradient descent) failed completely under Byzantine attacks, often diverging or settling on wildly incorrect allocations.
  • Superiority over BREDA: The proposed dual-domain algorithms achieved significantly lower "dual consensus error" than BREDA. In the IEEE 118-bus test, the proposed method reached nearly perfect consensus on the shadow price, whereas BREDA's dual variables remained scattered.
  • Robustness to Attack Scale: The performance of the dual-domain defense remained steady even as the number of Byzantine agents in the network increased, proving its scalability.

Limitations and Future Work

  • Deterministic Focus: The current theoretical analysis assumes deterministic cost functions. The authors note that extending this to stochastic settings (where data is noisy even without attacks) is a necessary next step.
  • Network Sparsity: The effectiveness of robust aggregation rules often depends on nodes having enough "honest" neighbors to outvote the malicious ones. In very sparse networks, the required conditions for convergence might be harder to meet.
  • Online Optimization: The paper focuses on static resource allocation. Future work could explore online versions where resource demands and costs change in real-time.

Summary updated

Abstract

This paper investigates the problem of decentralized resource allocation in the presence of Byzantine attacks. Such attacks occur when an unknown number of malicious agents send random or carefully crafted messages to their neighbors, aiming to prevent the honest agents from reaching the optimal resource allocation strategy. We characterize these malicious behaviors with the classical Byzantine attacks model, and propose a class of Byzantine-resilient decentralized resource allocation algorithms augmented with dual-domain defenses. The honest agents receive messages containing the (possibly malicious) dual variables from their neighbors at each iteration, and filter these messages with robust aggregation rules. Theoretically, we prove that the proposed algorithms can converge to neighborhoods of the optimal resource allocation strategy, given that the robust aggregation rules are properly designed. Numerical experiments are conducted to corroborate the theoretical results.
BibTeX
@article{wang2024dual,
  author = {Runhua Wang and Qing Ling and Zhi Tian},
  title = {{Dual-Domain Defenses for Byzantine-Resilient Decentralized Resource Allocation}},
  journal = {IEEE Transactions on Signal and Information Processing Over Networks},
  year = {2024},
  doi = {10.1109/tsipn.2024.3485508},
}

Loading related content...

Figure