BASGD: Buffered Asynchronous SGD for Byzantine Learning

Yi-Rui Yang, Wu-Jun Li

TL;DR

Buffered Asynchronous SGD (BASGD) is a novel distributed learning algorithm designed to withstand malicious (Byzantine) attacks without requiring the central server to store any private training data. By introducing a clever buffered aggregation mechanism, it achieves the speed and flexibility of asynchronous training while maintaining the robust security typically only found in slower, synchronous methods.

What Problem Does This Paper Address?

In distributed machine learning paradigms like federated learning or edge computing, a central server aggregates model updates (gradients) from multiple remote workers. However, these networks are vulnerable to "Byzantine" workers—nodes that send corrupted data due to hardware failures, software bugs, or intentional malicious attacks.

Existing defenses generally fall into two camps, both of which have fatal flaws for real-world use:

  1. Synchronous Byzantine Learning (SBL): The server waits for all workers to send their gradients before aggregating them. This is secure but impractically slow, as the entire system is bottlenecked by the slowest worker (stragglers) or offline nodes.
  2. Asynchronous Byzantine Learning (ABL): Workers update the server independently without waiting. While fast, existing ABL methods either completely fail against intentional malicious attacks (e.g., Kardam) or require the central server to hold a clean dataset to "test" incoming gradients (e.g., Zeno++), which violates the strict data privacy requirements of federated learning.

The authors tackle this gap by asking: Can we build an asynchronous learning method that resists malicious attacks without ever storing training data on the server?

Methods

To solve this, the authors introduce Buffered Asynchronous SGD (BASGD). The core idea is to bridge the gap between synchronous and asynchronous updates using a buffer system on the server.

Illustration of the BASGD buffer system mapping workers to server buffers.
  • The Buffer System: The server maintains $B$ buffers. When a worker sends a gradient, it is temporarily stored in a specific buffer (determined by a modulo operation on the worker's ID).
  • Semi-Asynchronous Aggregation: From the worker's perspective, the system is fully asynchronous—they send a gradient, immediately receive the latest model weights, and keep working. However, the server waits until all $B$ buffers contain at least one gradient. Once full, the server applies a robust aggregation function (like coordinate-wise median or trimmed-mean) to the buffered gradients to update the global model.
  • Buffer Reassignment (Straggler Mitigation): To prevent a dead or heavily delayed worker from leaving a buffer empty and stalling the whole system, BASGD uses a timer ($\Delta$). If the timer expires before all buffers are full, the server flushes the buffers and reassigns the currently active workers to new buffers, ensuring the pipeline keeps moving.

Datasets

The authors evaluated BASGD on two standard benchmarks:

  • Image Classification (IC): CIFAR-10 dataset using a ResNet-20 model.
  • Natural Language Processing (NLP): WikiText-2 dataset using an LSTM network.

Key Insights and Ideas

  • Privacy-Preserving Resilience: By relying purely on the geometric properties of the buffered gradients (e.g., taking the median of the buffers) rather than scoring them against a server-held validation set, BASGD preserves the strict data privacy required in modern distributed learning.
  • Why Existing Asynchronous Defenses Fail: The authors discovered exactly why previous filter-based ABL methods like Kardam fail under malicious attacks. To successfully filter out cleverly disguised malicious gradients, Kardam ends up throwing away massive amounts of loyal gradients (up to ~89% in their tests), effectively destroying the learning process.
  • A Universal Converter: BASGD essentially acts as a framework to convert existing synchronous robust aggregation rules (which are well-studied) into asynchronous ones, opening the door for many new ABL algorithms.

Key Results

  • Theoretical Guarantees: The authors mathematically prove that BASGD converges at a rate of $O(1/\sqrt{T})$, which matches the convergence rate of vanilla, undefended Asynchronous SGD (ASGD). It incurs only a constant variance penalty as the "tax" for its Byzantine resilience.
  • Survival Under Attack (CIFAR-10): Under a "Negative Gradient" (malicious) attack with 3 to 6 Byzantine workers, vanilla ASGD and Kardam completely collapsed, with accuracy plummeting to around 10%. In contrast, BASGD successfully converged, maintaining a top-1 accuracy of over 80%.
Performance comparison of BASGD against baselines under no attack and NG-attacks.
  • Stable NLP Training (WikiText-2): Under similar attacks, the baseline methods saw their perplexity (error) explode to unusable levels. BASGD converged smoothly, suffering only a minor perplexity penalty compared to a completely attack-free gold standard.
  • The Buffer Trade-off: The experiments confirmed that while larger buffer sizes ($B$) increase resilience against more attackers, they slightly degrade baseline accuracy and slow down the update frequency.

Limitations and Future Work

  • Wall-Clock Speedup: While the paper proves theoretical convergence and resilience, the authors note that a thorough empirical study of the actual wall-clock speedup (compared to strictly synchronous methods) is left for future work.
  • Theoretical Tightness: The mathematical bounds regarding the maximum delay/staleness parameter ($\tau_{max}$) might not be perfectly tight. The authors acknowledge that further theoretical work is needed to fully reveal the tightness of this parameter in asynchronous Byzantine learning.

Summary updated

Abstract

Distributed learning has become a hot research topic due to its wide application in cluster-based large-scale learning, federated learning, edge computing and so on. Most traditional distributed le...
BibTeX
@article{yang2023basgd,
  author = {Yi-Rui Yang and Wu-Jun Li},
  title = {{BASGD: Buffered Asynchronous SGD for Byzantine Learning}},
  journal = {J. Mach. Learn. Res.},
  year = {2023},
}
Figure