Decentralized learning lets a group of devices train a shared model by exchanging updates only with nearby peers, with no central server. Two problems make this hard in practice. First, some peers may be faulty or malicious; these are called Byzantine nodes. The standard defense is the trimmed mean: each device sorts what its neighbors sent, discards the most extreme values, and averages the rest. Second, on moving platforms such as drone swarms, vehicles, or satellites, neighbors appear and vanish within seconds. Trimming only works when a device hears from enough neighbors in a given round, typically at least $2F+1$ or $3F+1$ of them when up to $F$ might lie. Mobile networks routinely fall below that count, and today the only safe choice is to stop collaborating for that round.
We propose to trim over a short window of time rather than within a single round. Each device keeps a small buffer holding the latest message from every peer it has recently heard from. It trims and averages over that buffer. It also scales how quickly it forgets past corrections according to how well connected it has recently been. The device cannot see the global network, only its own contact history, so both choices must be made from local information. The research question is whether this trade can be analyzed and controlled: older messages raise the neighbor count enough for trimming to work, but they bring two costs. They introduce drift from out-of-date information, and over a longer window a device may meet more distinct malicious peers.
Core Claim
The closest prior work is BRED (Improving the Robustness-Utility Trade-off in Decentralized Learning over Sparse Networks). It combines robust aggregators with Exact Diffusion, a bias-corrected decentralized method that keeps a running "dual" correction term at each node. BRED adds a leak factor $q\in(0,1)$ to that term so that adversarial errors are forgotten rather than accumulated. This cuts the start-up cost from $\mathcal{O}((1-\lambda)^{-6})$ to $\mathcal{O}((1-\lambda)^{-2})$, where $1-\lambda$ is the spectral gap, a standard measure of how fast information mixes across the graph. BRED assumes a fixed, undirected graph and a hand-tuned static $q$ (it reports $q=0.7$ as an "empirical sweet spot").
Our claim is that on time-varying graphs a single static $q$ is wrong in a predictable direction. During outages the correction term decays before legitimate information can arrive to refresh it. During dense contact it retains more than it needs. Leaking according to a locally estimated effective gap, combined with windowed trimming, should recover cooperative gains in exactly the regimes where per-round trimming would fall back to local training.
Concretely, agent $i$ at time $t$ holds a buffer $\mathcal{B}_i(t)$ with one entry per peer ID heard within the last $\tau$ steps. Each entry is $(x_j, a_j)$, where $a_j$ is the age of the message measured by the receiver's own clock. The aggregate is
$$ \hat{x}_i(t) = \sum_{k=F+1}^{m-F} \frac{w_{(k)}}{\sum_{l=F+1}^{m-F} w_{(l)}}\, x_{(k)}, \qquad w_{(k)} = \max\!\left(e^{-\kappa a_{(k)}},\, w_{\min}\right), $$
where $m=|\mathcal{B}_i(t)|$ and $x_{(k)}$ is the $k$-th smallest buffered value in each coordinate. $F$ entries are removed from each end by count, and the decay rate $\kappa$ and floor $w_{\min}$ down-weight stale survivors only after trimming.
The ordering matters. Weighting by freshness before trimming, as the delay-decay weights in CoDynTrust effectively do, creates an attack. A Byzantine node can simply broadcast every step, always appear fresh, and outweigh stale honest peers. Counting first and weighting second closes that route.
The leak becomes $q_i(t)=g(\hat{\gamma}_i(t))$. Here $\hat{\gamma}_i$ is a local proxy for the effective spectral gap, computed from agent $i$'s own recent degree and contact-renewal rate, and $g$ is chosen from the bound we derive.
"Partial observability" enters in a specific sense. No agent sees the topology, the global spectral gap, or which peers are honest. The method must act on local observations of the network, just as agents in a Dec-POMDP act on local observations of the environment.
Research Program
The theoretical part extends BRED's analysis from a fixed mixing matrix to $B$-interval-connected time-varying graphs, meaning graphs whose union over every $B$ consecutive steps is connected. We then add the windowed buffer. We expect the honest-node error to split into three terms. The first is a trimming term: residual Byzantine influence, scaled by the variance of honest messages, as in Su et al.. The second is a staleness term that grows with $\tau$ and the step size. The third is a dual-leak term: it shrinks as $q\to 0$ but costs bias that scales inversely with the effective gap over the window.
The safety condition also changes. Instead of a minimum instantaneous degree, the requirement becomes that the window contains at least $2F_\tau+1$ distinct peers, where $F_\tau$ bounds the Byzantine IDs a node can meet within $\tau$ steps. This makes the window trade-off explicit: a longer window helps the count of distinct peers but can also increase $F_\tau$. Choosing $\tau$ and $q$ to balance these terms yields the local rule $g$. If the bound turns out to be too loose to guide tuning, we will fit $g$ on held-out mobility patterns and report that honestly as a heuristic.
The algorithmic part builds the aggregator on top of BRED and BRED-M (its momentum variant), so that any gain is attributable to the two new pieces.
The application part tests whether the same mechanism helps when the shared quantities are policy parameters of agents that only partially observe their environment. Here the communication graph is induced by proximity, so it changes as agents move.
Prior work frames the gap from three sides.
- Asynchronous threshold-meeting. ADHT (Byzantine-Resilient Distributed Hypothesis Testing With Time-Varying Network Topology) already meets a $2f+1$ threshold asynchronously by storing historical beliefs. It does so over a discrete hypothesis set, where staleness does not cause optimization drift. We carry the idea into continuous optimization and bound that drift.
- Fixed per-step degree. The resilient bandit work (Byzantine-Resilient Decentralized Multi-Armed Bandits) handles time-varying random graphs but requires $3f+1$ neighbors at every step.
- Penalty instead of trimming. The total-variation approach (Byzantine-robust decentralized stochastic optimization over static and time-varying networks) handles time-varying graphs by penalizing differences between neighbors rather than trimming. It pays a residual optimality gap controlled by its penalty weight.
None of these three combines bias correction, trimming, and graphs whose connectivity varies over time.
Two further papers constrain the design. The W-MSR defense with a synchronized safe policy (Secure Multi-agent Reinforcement Learning for Service Systems) works, but it needs shared random seeds and a static graph. Our method uses neither. EIR-MAPPO (Byzantine Robust Cooperative Multi-Agent Reinforcement Learning as a Bayesian Game) relies on a centralized critic. We avoid one deliberately, because COMRAD reports that decentralized independent PPO beat centralized-training methods on a role-asymmetric task.
Baselines
Naive reference points. The do-nothing baseline is purely local training, in which no messages are exchanged. Its counterpart is per-round trimming with fallback: the agent cooperates only in rounds where its instantaneous degree meets the threshold and otherwise takes a local step. This is what existing guarantees permit.
Strongest existing method. The strongest competitor is BRED-M from Improving the Robustness-Utility Trade-off in Decentralized Learning over Sparse Networks. It is the only method in the file with bias correction, trimming, and the improved start-up cost on sparse graphs. Its reported number is "approximately 56% accuracy" on CIFAR-10 with ResNet-18 on a sparse ring with 25% Byzantine attackers. Standard robust decentralized SGD baselines "collapsed to roughly 29% or failed to converge entirely" in the same setting. We will first reproduce the roughly 56% figure on the static ring. We will then run BRED-M on dynamic graphs using last-known neighbor messages and a static $q$. That $q$ is tuned per graph family by grid search over the same budget we give our method: same seeds, data partitions, steps, and number of tuning runs. No reported result for BRED on time-varying graphs was found on Lacuna, so these numbers will be new.
Penalty-based competitor. We also run the total-variation method from Byzantine-robust decentralized stochastic optimization over static and time-varying networks, tuning its penalty weight over the same budget. That paper reports only qualitative MNIST results, for example that it is "best among the robust methods" under same-value attacks. No numerical figure was found on Lacuna.
Ablations. Three ablations isolate the key ingredients:
- windowed buffer with static $q$;
- adaptive $q$ with per-round trimming;
- freshness weighting applied before trimming, which demonstrates the attack described in the Core Claim.
What counts as beating BRED-M. Our method beats the tuned static-$q$ BRED-M if its final honest-node accuracy, averaged over at least five seeds, exceeds BRED-M's by more than the seed-to-seed spread on mobility graphs with outages. It must also not lose on the static ring. Matching BRED-M everywhere would mean the adaptive leak adds nothing.
Why not just…?
Why not just keep BRED with a well-tuned static $q$ and the last message from each neighbor? This is the real threat. If mobility statistics are stationary, one tuned $q$ may already sit near the optimum, and a last-known-message buffer is essentially our window with $\tau=\infty$ and no decay. We therefore treat it as the main baseline rather than a straw man.
The proposal is justified only if two things hold. First, on graphs whose connectivity changes regime within a run (dense convoys alternating with sparse dispersal), the tuned static $q$ is measurably worse than the adaptive one. Second, an unbounded buffer is beaten by a bounded one under the staleness and ID-accumulation attacks below. If neither appears, we will report that static tuning suffices. The remaining contribution would then be the analysis explaining why.
Why not just fall back to local updates when the neighbor count is too low? The bandit paper shows this is safe: its no-harm guarantee is relative to single-agent UCB1. The cost is forfeited cooperation. The perception benchmarks show how large that cost can be when partial views are complementary: V2X-Sim reports fusion gains of up to 41.1% [email protected] over single-agent detection. Our experiments will report the fraction of rounds in which each method is allowed to cooperate, alongside accuracy, so the gap is visible directly.
Why not use the total-variation penalty, which already handles time-varying graphs? It avoids trimming but trades consensus against accuracy through its penalty weight. The research file notes it degrades as the Byzantine fraction grows and lacks the improved start-up cost of bias-corrected methods. We test it head to head at Byzantine fractions of 10%, 25%, and 33%. If it matches our method at low fractions, that is a fair result and we will say so.
Why not let agents use predicted topology, since satellite orbits are deterministic? For LEO constellations, time-indexed snapshot graphs (Jia et al.) could supply the true future gap. We include this as an oracle: $q$ is set from the true windowed spectral gap. It upper-bounds what local estimation can achieve, and the size of the gap to the oracle measures how much partial observation of the network costs.
Proposed Experiments
Supervised benchmarks. We use MNIST softmax regression and CIFAR-10 with ResNet-18 under Dirichlet non-i.i.d. splits, following the BRED and total-variation papers. Graph families are:
- a static ring, for the sanity reproduction;
- time-varying Erdős–Rényi graphs;
- random-waypoint proximity graphs with tunable speed, so that contact duration can be swept;
- a periodic contact schedule mimicking a satellite constellation.
Attacks include sign-flipping, same-value, and zero-sum attacks from prior work, plus two new ones. In the staleness attack, Byzantine nodes broadcast every step to stay fresh while sending values just inside the honest range. In the mobility attack, Byzantine nodes move to meet many honest agents within a window, which inflates $F_\tau$.
Metrics are mean and worst honest-node test accuracy, consensus distance among honest nodes, fraction of rounds with permitted cooperation, and wall-clock steps to reach a target accuracy.
Decisive checks. Three outcomes would settle the question:
- On the static ring, our method must land near BRED-M's roughly 56%; a large deviation means an implementation error.
- As node speed increases, per-round trimming should fall toward local-only accuracy, while windowed trimming should degrade more slowly.
- Under the mobility attack, longer windows should eventually hurt, at a crossover predicted by the $F_\tau$ term. Observing that crossover where the analysis predicts is the strongest evidence the theory describes reality.
Bandit test. We use the synthetic decentralized bandit testbed with 10 agents and 2 attackers, removing the per-step $3F+1$ degree condition. We check whether windowed trimming keeps regret logarithmic while the original resilient algorithm must revert to single-agent behavior. The source paper reports only the $\mathcal{O}(\log T)$ rate, not regret values.
Partially observed multi-agent RL. In Level-Based Foraging, agents run decentralized PPO and average actor and critic parameters only with agents within communication range, so the graph moves with the agents. Some agents send corrupted parameters. EIR-MAPPO reports roughly 5.8% improvement on Level-Based Foraging under attack. Because it uses a centralized critic, we include it as a reference rather than a like-for-like competitor. We also include independent PPO with no sharing, which COMRAD shows can be surprisingly strong. A positive result would show that proximity-based parameter sharing with windowed trimming beats both independent PPO and naive averaging under attack, without a central critic or shared random seeds.
References
- Improving the Robustness-Utility Trade-off in Decentralized Learning over Sparse Networks
- CoDynTrust: Robust Asynchronous Collaborative Perception via Dynamic Feature Trust Modulus
- Byzantine-Resilient Distributed Hypothesis Testing With Time-Varying Network Topology
- Byzantine-Resilient Decentralized Multi-Armed Bandits
- Byzantine-robust decentralized stochastic optimization over static and time-varying networks
- Secure Multi-agent Reinforcement Learning for Service Systems with Affinity and Byzantine Nodes: Stability Analysis and Protection Design
- Byzantine Robust Cooperative Multi-Agent Reinforcement Learning as a Bayesian Game
- COMRAD: A Benchmark for Embodied Cooperative Multi-Agent Reinforcement Learning
- V2X-Sim: Multi-Agent Collaborative Perception Dataset and Benchmark for Autonomous Driving
- Service Function Chain Dynamic Scheduling in Space-Air-Ground Integrated Networks