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.

    Source: §I · p. 1

  • Method

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

    Source: §I · p. 2, B. Drift Dynamics and the BPI Score · p. 4

  • Results

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

    Source: §I · p. 2, §VII · p. 9

  • Takeaways & Limitations

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

    Source: §VII · pp. 9–10

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

    Source: C. Relaxing the Attacker’s Objective… · p. 5

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.Source: §I · p. 1
  • 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.Source: Figure 1 · p. 1, §I · p. 1
  • Existing evaluations use random, fixed, ad hoc, or topology-based placements, leaving no common criterion for selecting a Byzantine set by finite-time influence.Source: §I · p. 1, §II · p. 2
  • The attacker selects m participants to maximize finite-time impact on honest nodes under a communication topology and training horizon T.Source: §I · p. 2
  • 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.Source: §I · p. 2
  • Experiments show BPI-guided placement strengthens attacks across heterogeneous topologies and poisoning objectives, while placement can also alter apparent Byzantine-robust aggregation.Source: §I · p. 2

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.Source: A. Topology and Byzantine Placement in… · p. 2, §III · p. 3
  • Several studies evaluate random, regular, small-world, ring, or other graphs while fixing or randomly selecting Byzantine nodes without topology-aware optimization.Source: A. Topology and Byzantine Placement in… · p. 2
  • ClippedGossip uses topology-specific or ad hoc placements, including attaching Byzantine workers to randomly selected honest workers in some experiments.Source: A. Topology and Byzantine Placement in… · p. 2
  • 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.Source: A. Topology and Byzantine Placement in… · p. 2
  • 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.Source: A. Topology and Byzantine Placement in… · pp. 2–3
  • 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.Source: A. Topology and Byzantine Placement in… · p. 3
  • The model uses a connected undirected graph with n nodes, local objectives, and repeated neighbor exchanges through a doubly-stochastic gossip matrix W.Source: §III · p. 3
  • As gossip iterations increase, messages converge toward uniform network mixing, whereas finite-time behavior depends on the topology and placement.Source: §III · p. 3

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.Source: A. Byzantine Threat Model · p. 3
  • 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.Source: A. Byzantine Threat Model · p. 3
  • Robust aggregation makes effective mixing nonlinear and time-varying because acceptance and weighting depend on attacks, data, trajectories, and prior rounds.Source: A. Byzantine Threat Model · p. 4
  • The attacker chooses the size-m placement that maximizes expected honest-node drift after T rounds over training randomness ξ.Source: A. Byzantine Threat Model · p. 4
  • Evaluating one placement requires paired training runs across random seeds, making exhaustive optimization over possible placements infeasible for moderately sized graphs.Source: A. Byzantine Threat Model · p. 4
  • BPI is introduced as a tractable proxy for identifying influential Byzantine placements.Source: A. Byzantine Threat Model · p. 4

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.

Drift Dynamics

BPI Score

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.

Greedy Selection

Greedy Selection

  • Greedy optimization costs O(m·n·T·|E|) when each BPI evaluation is computed iteratively.Source: A. Greedy BPI Selection · p. 5
  • Greedy selection is not guaranteed to find the global optimum because marginal gains depend on prior selections and diffusion patterns may overlap.Source: A. Greedy BPI Selection · p. 5

Local Search

  • SWAP-BPI refines the greedy set by repeatedly replacing a selected node with an unselected node whenever the replacement increases BPI.Source: A. Greedy BPI Selection · p. 6

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.Source: B. Local Search Refinement via 1-Swap · p. 6
  • 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.Source: B. Local Search Refinement via 1-Swap · p. 6

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.Source: §VI · p. 6, Table II · p. 7

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.Source: §VI · pp. 6–7

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.Source: §VI · pp. 6–7

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

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.Source: 1) BPI Across Placement Strategies · p. 7, Figure 4 · p. 8

Structural baselines

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.Source: 2) Accuracy Drop on Untargeted Attacks · p. 8

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.Source: 2) Accuracy Drop on Untargeted Attacks · p. 8

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.Source: C. Transferability Across Attack… · p. 8

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.Source: C. Transferability Across Attack… · p. 8

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.Source: C. Transferability Across Attack… · p. 8

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.Source: C. Transferability Across Attack… · pp. 8–9

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.Source: D. Beyond Linear Gossip (RQ4) · p. 9
  • 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.Source: D. Beyond Linear Gossip (RQ4) · p. 9
  • 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.Source: D. Beyond Linear Gossip (RQ4) · p. 9
  • 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.Source: D. Beyond Linear Gossip (RQ4) · p. 9

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.Source: §VII · pp. 9–10

Related papers

Loading 2609.01495v1…