PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing Byzantine Node Placement in Decentralized Federated Learning

Edoardo Gabrielli, Gabriele Tolomei

arXiv:2609.01495v1cs.LGcs.AI

TL;DR

DFL security evaluations often overlook which participants are compromised, although graph position determines how Byzantine influence propagates within finite training horizons. The paper introduces BPI, a gossip-dynamics-based placement criterion and efficient optimization algorithms, finding damaging placements across heterogeneous topologies and attacks, including under robust aggregation.

  • Problem

    DFL threat models and evaluations lack a common criterion for choosing which participants to compromise according to their finite-time influence on honest nodes.

  • Method

    BPI estimates a Byzantine set’s cumulative finite-time exposure from gossip dynamics, enabling efficient placement optimization without executing training for every candidate.

  • Results

    BPI-guided placements consistently identify highly damaging configurations across heterogeneous graph families and poisoning objectives, including when Byzantine-robust aggregation relaxes linear gossip.

  • Takeaways & Limitations

    Byzantine placement should be specified and optimized as part of DFL security evaluation.

  • Takeaways & Limitations

    BPI linearizes the learning process, ignoring local SGD noise and data heterogeneity while abstracting away exogenous randomness.

Abstract

from arXiv · show

Security evaluations of decentralized federated learning (DFL) typically focus on how Byzantine participants behave, while largely overlooking which participants are compromised. Yet, because aggregation is distributed over a communication graph, the placement of Byzantine nodes determines how malicious influence propagates through the network. We therefore treat Byzantine placement as an explicit adversarial decision and formulate the attacker's objective as selecting, under a fixed compromise budget, the set of participants that maximizes its finite-time impact on honest nodes. To approximate this objective without executing the learning process for every candidate placement, we introduce Byzantine Placement Influence (BPI), a set-level measure derived from the actual gossip dynamics that quantifies the cumulative exposure of honest nodes to Byzantine sources over the training horizon. Unlike placement criteria based on node centrality heuristics, BPI directly accounts for weighted multi-hop propagation and interactions among compromised nodes. We develop efficient algorithms for optimizing BPI and evaluate them across six heterogeneous graph families, untargeted model poisoning, and backdoor attacks. BPI-guided placements consistently identify highly damaging configurations across different network structures and remain effective when the linear gossip assumption is relaxed through Byzantine-robust aggregation. Our results show that Byzantine placement is a critical but under-modeled dimension of DFL threat models and robustness evaluations.

I. INTRODUCTION

DFL makes Byzantine placement an adversarial decision because graph position controls finite-time propagation to honest nodes. The paper formulates placement optimization and introduces BPI to identify damaging sets efficiently across topologies and attacks.

  • DFL distributes aggregation across participants, so malicious information propagates through successive graph-based aggregations rather than reaching every client immediately.
  • The same number of Byzantine nodes can produce substantially different effects when compromised participants occupy different network positions.Figure 1 contrasts limited exposure from poor placement with broader reach from strategic placement within the same training horizon.
  • Existing evaluations use random, fixed, ad hoc, or topology-based placements, leaving no common criterion for selecting a Byzantine set by finite-time influence.
  • The attacker selects m participants to maximize finite-time impact on honest nodes under a communication topology and training horizon T.
  • BPI measures cumulative finite-time exposure from a Byzantine set using gossip dynamics and supports efficient high-influence placement algorithms without executing training for every candidate.
  • Experiments show BPI-guided placement strengthens attacks across heterogeneous topologies and poisoning objectives, while placement can also alter apparent Byzantine-robust aggregation.

A. Topology and Byzantine Placement in Decentralized Learning

Prior work uses heterogeneous topologies and placement conventions, often without optimizing compromised nodes. This paper instead derives placement influence from gossip dynamics rather than centrality or shortest-path heuristics.

  • In fully connected networks, all nodes are structurally equivalent, making Byzantine placement essentially irrelevant.
  • Several studies evaluate random, regular, small-world, ring, or other graphs while fixing or randomly selecting Byzantine nodes without topology-aware optimization.
  • ClippedGossip uses topology-specific or ad hoc placements, including attaching Byzantine workers to randomly selected honest workers in some experiments.
  • The literature lacks a common placement convention, making attack and defense results harder to compare and leaving compromise selection outside the attacker’s optimization problem.
  • MaxSpAN-FL favors well-separated attackers using BFS influence regions and shortest-path separation, but its evaluation covers one FGSM datapoisoning attack and three graph families.
  • BPI derives a common finite-time placement criterion from gossip dynamics, accounting for communication topology across poisoning objectives instead of relying on centrality or shortest-path separation.
  • The model uses a connected undirected graph with n nodes, local objectives, and repeated neighbor exchanges through a doubly-stochastic gossip matrix W.
  • As gossip iterations increase, messages converge toward uniform network mixing, whereas finite-time behavior depends on the topology and placement.

A. Byzantine Threat Model

The threat model assumes an external attacker selects a fixed-size Byzantine set before training, while honest-node impact is defined through expected drift after T rounds. Directly optimizing this objective is infeasible because each candidate placement requires repeated training under randomness.

  • The attacker selects m Byzantine nodes before training, with Byzantine nodes performing model or data poisoning attacks.
  • The model assumes a fixed topology, complete Byzantine-set knowledge, and non-robust linear aggregation.Under these assumptions, the mixing matrix depends only on topology.
  • Robust aggregation makes effective mixing nonlinear and time-varying because acceptance and weighting depend on attacks, data, trajectories, and prior rounds.
  • The attacker chooses the size-m placement that maximizes expected honest-node drift after T rounds over training randomness ξ.
  • Evaluating one placement requires paired training runs across random seeds, making exhaustive optimization over possible placements infeasible for moderately sized graphs.
  • BPI is introduced as a tractable proxy for identifying influential Byzantine placements.

A. From Empirical Drift to a Tractable Proxy

Finite-time propagation determines whether a Byzantine perturbation reaches honest nodes strongly enough to persist, motivating a topology-aware proxy based on linearized gossip dynamics. BPI aggregates weighted exposure over the training horizon and evaluates placements jointly rather than through independent centrality scores.

  • Finite-time propagation matters because small biases may disappear when Byzantine sources occupy low-influence regions, while backdoor effects may survive only for limited hops.
  • The proxy captures finite-time Byzantine exposure without requiring training runs to maximize the adversarial objective.
  • Drift Dynamics: The linearized drift recursion propagates accumulated drift through W and injects fresh perturbations from Byzantine sources at each round.
  • Drift Dynamics: The term (W1_B)_i is the total mixing weight that honest node i assigns to Byzantine neighbors.
  • BPI Score: BPI averages total honest-node exposure to Byzantine sources accumulated over T rounds and depends only on W, B, and T.
  • BPI Score: Unlike degree, betweenness, and eigenvector centrality, BPI captures joint diffusion among the Byzantine set and finite-time propagation.

C. Relaxing the Attacker’s Objective with BPI

The paper replaces the intractable attacker objective with maximizing BPI over fixed-size Byzantine sets, then approximates that optimization using greedy selection and local search. The proxy remains limited by its linearization and by the computational cost of exact placement search.

  • Maximizing BPI over placements of size m provides a tractable approximation to maximizing expected honest-node drift.
  • BPI ignores local SGD noise, data heterogeneity, and exogenous training randomness ξ because it linearizes only the gossip component.
  • Greedy Selection: Greedy-BPI incrementally adds the candidate node producing the largest BPI value at each step until m nodes are selected.
  • Exact optimization remains impractical because it requires evaluating all possible Byzantine placements, motivating efficient heuristic algorithms.
  • Greedy Selection: Greedy optimization costs O(m·n·T·|E|) when each BPI evaluation is computed iteratively.
  • Greedy Selection: Greedy selection is not guaranteed to find the global optimum because marginal gains depend on prior selections and diffusion patterns may overlap.
  • Local Search: SWAP-BPI refines the greedy set by repeatedly replacing a selected node with an unselected node whenever the replacement increases BPI.

B. Local Search Refinement via 1-Swap

The refinement procedure improves a greedy BPI placement through exhaustive single-node swaps, producing a set locally optimal under all 1-swap moves. Experiments evaluate placement strategies across six sparse, structurally different topologies and two poisoning objectives.

  • Local search refinement: Swap search tests every single exchange between a Byzantine node and an unselected node, accepting the exchange with the largest ΦT improvement.The process repeats until no improving exchange remains, yielding local optimality with respect to 1-swap moves.
  • Local search refinement: Each accepted swap strictly increases or preserves the BPI objective, and finite feasible placements guarantee termination.A swap iteration evaluates m(n −m) exchanges at O(T · |E|) cost per objective evaluation.
  • Experimental design: The main setup uses 50 participants, five Byzantine nodes, and 30 communication rounds across six sparse graph families with average degrees approximately four to five.Graphs retain substantially different structures while avoiding trivial explanations based on network density.
  • Attack objectives: Untargeted experiments use aligned additive FixedBias perturbations, while targeted experiments use BadNets with a 3 × 3 trigger and target class y∗= 0.FixedBias uses α = 64 and scales perturbations to each attacker’s initial model norm; BadNets poisons 20% of local data.
  • Evaluation: Evaluation compares exposure ordering, accuracy degradation, and backdoor attack success across placement strategies and research questions RQ1–RQ4.RQ4 tests whether BPI placement remains effective with nonlinear Byzantine-robust aggregation.

A. Empirical Validation of Finite-Time Exposure (RQ1)

On a 50-node Ring-of-Cliques topology, empirical honest-model drift follows the ordering predicted by finite-time BPI exposure. The largest-exposure Swap-BPI placement produces the largest drift throughout training.

  • Empirical validation: Empirical drift trajectories preserve the ordering of placements by increasing ΦT (W, B) under FixedBias.Minimum exposure yields limited drift, while Eigenvector, Random, and Swap-BPI produce progressively faster and larger accumulation.
  • Empirical validation: Swap-BPI has the largest ΦT (W, B) and the largest empirical drift throughout training.The comparison spans placements with progressively larger finite-time exposure on Ring-of-Cliques.
  • Empirical validation: Greater finite-time exposure results in faster and larger drift of honest models across communication rounds.Figure 3 tracks the evolution of empirical drift D(t).

B. Cross-Topology Consistency of BPI (RQ2)

Across six heterogeneous graph families, BPI-guided placements consistently reach the high-exposure tail and achieve the strongest mean accuracy degradation. Structural heuristics vary substantially in effectiveness across topologies.

  • BPI across topologies: Greedy-BPI and especially Swap-BPI consistently locate placements at the extreme high-exposure end across all six graph families.Figure 4 compares deterministic strategies with 5000 uniformly sampled five-node placements; farther-right positions indicate greater exposure.
  • Structural baselines: No conventional structural heuristic provides a uniformly strong placement across graph families.Their relative quality changes markedly with topology and can approach the random-placement distribution on some graphs.
  • Structural baselines: Degree and Betweenness reach 19.6 and 19.4 percentage points on Scale-Free, but on Random-Geometric fall to 15.3 and 14.0 versus 20.8 for Greedy-BPI.They provide little advantage over Random on Ring-of-Cliques and Dragonfly.
  • Structural baselines: MaxSpAN-FL performs strongly on Ring-of-Cliques, Dragonfly, and Random-Geometric but is weaker on Scale-Free, DC-SBM, and Core-Periphery.Eigenvector centrality is weakest on Ring-of-Cliques, Dragonfly, and Random-Geometric.
  • BPI results: Either Greedy-BPI or Swap-BPI achieves the largest mean degradation on every evaluated topology.Topology-averaged degradations are 20.8 and 20.9 percentage points, respectively, with only a small difference between methods.
  • Interpretation and limitation: Swap-BPI is guaranteed to improve or preserve BPI, not downstream accuracy degradation, because BPI is a proxy for complete learning dynamics.Small empirical inversions between Greedy-BPI and Swap-BPI are therefore expected.

C. Transferability Across Attack Objectives (RQ3)

BPI-guided placements transfer from aligned additive poisoning to BadNets backdoors and remain effective across graph families. Multi-hop propagation explains why malicious influence reaches non-neighboring honest nodes.

  • Structural baseline instability: MaxSpAN-FL is strongest on Dragonfly at 46.0% but drops to 29.7% on DC-SBM, while Eigenvector reaches only 14.7% ASR on Random-Geometric.Random placement is also topology-dependent, reaching 19.7% on Scale-Free and 17.0% on Core-Periphery.
  • Backdoor transfer: A BPI-guided strategy achieves the largest mean ASR on five of six graph families under BadNets.On Dragonfly, MaxSpAN-FL reaches 46.0% while Swap-BPI reaches 45.3%, a difference of 0.7 percentage points.
  • Transferability: BPI’s cross-topology stability persists although BadNets differs from the aligned additive model used to derive BPI.The result indicates that BPI captures a communication-process property rather than a FixedBias peculiarity.
  • Multi-hop propagation: Honest nodes can inherit and relay backdoors, allowing non-neighboring participants to acquire substantial ASR after several communication rounds.This propagation illustrates why one-hop degree alone cannot characterize placement influence.

D. Beyond Linear Gossip (RQ4)

Under nonlinear aggregation, changing only Byzantine identities substantially increases attack impact, showing that BPI-guided placement remains effective beyond linear gossip. The results also show that robust aggregation can leave topology-induced backdoor propagation intact, while the analysis remains bounded by static, known topologies and nominal linear-gossip assumptions.

  • Nonlinear aggregation: 99.8% versus 39.2% on Erdős–Rényi and 82.4% versus 16.0% on the Ring: Swap-BPI sharply increases BadNets ASRH over the original BALANCE placement.The experiments use n = 20 nodes and m = 4 Byzantine participants, with BALANCE as the nonlinear aggregation rule.
  • Nonlinear aggregation: Topology-aware placement exposes substantially more damaging BALANCE attack configurations than the original Byzantine placement.The original placement can make BALANCE appear robust because its Byzantine nodes are poorly positioned to influence the honest network.
  • Nonlinear aggregation: Robust aggregation does not necessarily attenuate topology-induced backdoor propagation and can yield higher ASRH than plain averaging under BadNets.Filtering changes relative neighbor influence, potentially favoring malicious updates that remain within the acceptance threshold.
  • Nonlinear aggregation: Under untargeted FixedBias poisoning, Swap-BPI causes a progressively larger accuracy gap over 300 rounds than the original BALANCE placement.This shows that placement effects persist beyond targeted backdoor attacks under nonlinear aggregation.
  • Scope: BPI-guided placement algorithms provide a practical way to identify high-influence Byzantine sets, but the analysis assumes static, known topologies and nominal linear gossip dynamics.Time-varying or partially known topologies and defense-specific propagation dynamics remain future extensions.
Loading 2609.01495v1…