Fast Machine Learning with Byzantine Workers and Servers

El Mahdi El Mhamdi, Rachid Guerraoui, Arsany Guirguis

TL;DR

This paper introduces LIUBEI, a novel machine learning algorithm designed to be resilient to Byzantine failures (arbitrary malicious behavior) in both workers and servers without significant communication overhead. LIUBEI achieves this by employing a unique filtering mechanism and a scatter/gather protocol, offering a practical solution for secure and robust distributed ML.

What Problem Does This Paper Address?

In distributed machine learning, especially with large datasets and models, components (workers and servers) can fail. A particularly challenging type of failure is "Byzantine" behavior, where a component acts arbitrarily and maliciously, potentially corrupting gradients or models. Existing solutions often focus on Byzantine workers or require significant communication overhead. This paper tackles the problem of achieving total Byzantine resilience (handling both worker and server failures) in a synchronous network setting with minimal communication overhead compared to standard non-Byzantine methods.

Methods

LIUBEI introduces two key innovations:

  • Novel Filtering Mechanism: Workers don't blindly trust parameter servers. Instead, they employ two filters:
  • Lipschitz Filter: Checks if a pulled model's growth (with respect to its gradient) is consistent with what's expected from a correct model, based on the loss function's Lipschitz continuity.
  • Models Filter: Bounds the difference between a worker's local model estimate and the pulled model, ensuring it's not drastically different from previous iterations. These filters allow workers to discard suspicious models from Byzantine servers without needing to communicate with all servers.

  • Scatter/Gather Protocol: The training process is divided into "scatter" phases (where servers work independently) and "gather" phases (where servers synchronize their models). This protocol helps bound the drift between models on correct servers with a small number of communication messages, preventing them from diverging too much.

LIUBEI also leverages existing Byzantine-resilient Gradient Aggregation Rules (GARs) like MDA to handle Byzantine workers.

Datasets

The paper uses standard image classification datasets for evaluation:

  • MNIST: A dataset of handwritten digits (70,000 images, 28x28 pixels, 10 classes).
  • CIFAR-10: A dataset of color images (60,000 images, 32x32 pixels, 10 classes).

They also evaluate with various model architectures, from small CNNs to larger ResNet models, to demonstrate scalability.

Key Insights and Ideas

  • Worker-side Server Verification: Instead of relying on a trusted server, LIUBEI empowers workers to actively verify the models they receive. This is a crucial shift in how Byzantine server failures are handled.
  • Balancing Communication and Resilience: The scatter/gather approach cleverly balances the need for model synchronization with the desire to minimize communication rounds, a common bottleneck in distributed ML.
  • Synergy of Filters: The combination of the Lipschitz and Models filters is more powerful than either alone, effectively catching different types of Byzantine attacks on servers.
  • Synchronous Network Advantage: By assuming network synchrony, LIUBEI can leverage simpler and more efficient mechanisms compared to asynchronous approaches, which often require more complex protocols.

Key Results

  • Accuracy: LIUBEI exhibits an accuracy loss of around 5% compared to vanilla TensorFlow in a Byzantine environment.
  • Convergence Overhead: The convergence overhead compared to vanilla TensorFlow is around 24%.
  • Throughput Gain: LIUBEI achieves a significant throughput gain of 70% compared to GuanYu, a state-of-the-art Byzantine-resilient algorithm that assumes network asynchrony.
  • Resilience: LIUBEI demonstrates resilience against various Byzantine server behaviors (Reversed, Partial Drop, Random, LIE attack) and Byzantine workers.
  • Scalability: The performance gain is emphasized with larger models, suggesting LIUBEI scales well with model complexity.

Limitations and Future Work

  • Data Dependency: The relationship between the frequency of the gather step and model variance is data-dependent and model-dependent. While LIUBEI provides safety guarantees, more frequent gathering might improve convergence speed but at the cost of increased communication. This trade-off remains an open question.
  • Optimal Bound on Variance: Finding the optimal bound on variance that guarantees both Byzantine resilience and convergence is still an open research question. The paper shows that unsatisfied variance assumptions can make GARs vulnerable to certain attacks.
  • GPU Performance: The current implementation uses CPUs. The authors expect that using GPUs would further emphasize the benefits of LIUBEI's reduced communication overhead.

Summary updated

Abstract

Machine Learning (ML) solutions are nowadays distributed and are prone to various types of component failures, which can be encompassed in so-called Byzantine behavior. This paper introduces LiuBei, a Byzantine-resilient ML algorithm that does not trust any individual component in the network (neither workers nor servers), nor does it induce additional communication rounds (on average), compared to standard non-Byzantine resilient algorithms. LiuBei builds upon gradient aggregation rules (GARs) to tolerate a minority of Byzantine workers. Besides, LiuBei replicates the parameter server on multiple machines instead of trusting it. We introduce a novel filtering mechanism that enables workers to filter out replies from Byzantine server replicas without requiring communication with all servers. Such a filtering mechanism is based on network synchrony, Lipschitz continuity of the loss function, and the GAR used to aggregate workers' gradients. We also introduce a protocol, scatter/gather, to bound drifts between models on correct servers with a small number of communication messages. We theoretically prove that LiuBei achieves Byzantine resilience to both servers and workers and guarantees convergence. We build LiuBei using TensorFlow, and we show that LiuBei tolerates Byzantine behavior with an accuracy loss of around 5% and around 24% convergence overhead compared to vanilla TensorFlow. We moreover show that the throughput gain of LiuBei compared to another state-of-the-art Byzantine-resilient ML algorithm (that assumes network asynchrony) is 70%.
BibTeX
@misc{mhamdi2019fast,
  author = {El Mahdi El Mhamdi and Rachid Guerraoui and Arsany Guirguis},
  title = {{Fast Machine Learning with Byzantine Workers and Servers}},
  year = {2019},
  eprint = {1911.07537},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.07537},
}
Figure