Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation

Jinbao Zhu, Hengxuan Tang, Songze Li, Yijia Chang

TL;DR

This paper introduces Generalized Lagrange Coded Computing (GLCC) codes, a novel framework for distributed computation that enhances resilience against slow workers (stragglers), protects against malicious data manipulation (adversarial workers), and ensures data privacy. GLCC codes offer a more flexible trade-off between communication and computation costs compared to existing methods, leading to significant speedups in distributed machine learning tasks.

What Problem Does This Paper Address?

In the era of big data, distributed computing is crucial for handling massive datasets and complex computations. However, this approach faces several challenges:

  • Straggler Effect: Slow or delayed worker nodes can significantly prolong overall computation time.
  • Adversarial Workers: Malicious workers might intentionally alter computation results for their own benefit, compromising data integrity.
  • Data Privacy: Sensitive data processed across multiple workers raises concerns about potential leakage, especially if workers collude.

Existing solutions, like Lagrange Coded Computing (LCC), offer some resilience and privacy but often have limitations in terms of straggler tolerance and flexibility in balancing system performance. This paper aims to address these limitations by proposing a more adaptable and robust coded computing framework.

Methods

The core contribution is the Generalized Lagrange Coded Computing (GLCC) codes. The key innovations include:

  • Dataset Partitioning: The dataset is divided into multiple groups.
  • Group-wise Encoding: Each group is encoded using carefully designed interpolating polynomials.
  • Redundant Data Sharing: Multiple encoded data points from each group are shared with each worker, creating computational redundancy.
  • Interference Cancellation: Workers generate responses that incorporate additional polynomials designed to cancel out interference between computation results from different groups at the master node.

This approach allows the master to decode the desired polynomial evaluations by interpolating the results, even in the presence of stragglers and adversarial workers. GLCC codes are a generalization of LCC codes, offering a more flexible trade-off between recovery threshold (number of workers needed), communication overhead, and computation complexity.

Datasets

The paper uses the following datasets for evaluating GLCC codes in the context of distributed machine learning:

  • MNIST: A dataset of handwritten digits, used for training 5 binary classifiers to distinguish between pairs of digits (0-1, 2-3, 4-5, 6-7, 8-9).
  • CIFAR-10: A dataset of images, used for training 5 binary classifiers to distinguish between specific object categories (e.g., airplane vs. cat). For CIFAR-10, a pre-trained VGG19 model was used to extract 512-dimensional feature representations.

Key Insights and Ideas

  • Flexible Trade-offs: GLCC codes introduce parameters (G for grouping, L for sub-responses) that allow for fine-tuning the system's performance. This means engineers can optimize for specific scenarios, balancing recovery threshold, communication, and computation.
  • Interference Cancellation is Key: The novel use of interference cancellation coefficients is crucial for combining results from different data groups efficiently, reducing download costs and enabling more robust decoding.
  • Privacy Through Noise: Information-theoretic privacy is achieved by adding random noise to the encoded data, ensuring that colluding workers cannot infer information about the original dataset.
  • Generalization Power: GLCC codes encompass LCC codes as a special case, demonstrating a clear evolutionary step in coded computing.
  • Practical Application: The framework is not just theoretical; it's shown to be effective in speeding up real-world machine learning tasks like distributed training.

Key Results

  • Speedup in Training: GLCC codes achieved significant speedups in training time compared to LCC codes. Specifically, up to 2.5-3.4x speedup was observed on MNIST and 3.4-3.9x speedup on CIFAR-10, depending on the straggler scenario and GLCC parameter configuration.
  • Lower Recovery Threshold: GLCC codes can achieve a lower recovery threshold, meaning fewer worker responses are needed to complete the computation, thus improving resilience to stragglers.
  • Enhanced Privacy: GLCC codes demonstrated a superior ability to tolerate more colluding workers (up to T=6) for privacy protection compared to LCC codes (up to T=3).
  • Performance Trade-offs: Experiments showed that different GLCC configurations (e.g., (G=1, L=2) vs. (G=5, L=1)) are optimal for different straggler scenarios, highlighting the flexibility of the approach. For mild straggler delays, a configuration with a lower computation load per worker might be preferred, while for severe delays, a configuration with a lower recovery threshold is more beneficial.

Limitations and Future Work

  • Quantization Losses: Applying GLCC codes to real-valued data (like machine learning models) requires quantization, which introduces accuracy losses. The paper notes that increasing quantization parameters can reduce these losses but risks overflow errors, creating a trade-off.
  • Finite Field Size: The required size of the finite field (q) for GLCC codes depends on parameters like M and L, which can impact computational efficiency.
  • Straggler Exploitation: The current work assumes stragglers provide no results. Future research could explore schemes that efficiently exploit partial computation results from slower workers.
  • Adversarial Tolerance Enhancement: While GLCC codes offer security against adversarial workers, the paper suggests further enhancing adversarial tolerance by incorporating ideas from existing works.
  • Analog Domain Application: Extending GLCC codes to operate in the analog domain is mentioned as an interesting future direction.

Summary updated

Abstract

We consider the problem of evaluating arbitrary multivariate polynomials over a massive dataset containing multiple inputs, on a distributed computing system with a leader node and multiple worker nodes. Generalized Lagrange Coded Computing (GLCC) codes are proposed to simultaneously provide resiliency against stragglers who do not return computation results in time, security against adversarial workers who deliberately modify results for their benefit, and information-theoretic privacy of the dataset amidst possible collusion of workers. GLCC codes are constructed by first partitioning the dataset into multiple groups, then encoding the dataset using carefully designed interpolating polynomials, and sharing multiple encoded data points to each worker, such that interference computation results across groups can be eliminated at the leader. Particularly, GLCC codes include the state-of-the-art Lagrange Coded Computing (LCC) codes as a special case, and exhibit a more flexible tradeoff between communication and computation overheads in optimizing system efficiency. Furthermore, we apply GLCC to distributed training of machine learning models, and demonstrate that GLCC codes achieve a speedup of up to $2.5-3.9\times $ over LCC codes in training time, across experiments for training image classifiers on different datasets, model architectures, and straggler patterns.
BibTeX
@article{zhu2025generalized,
  author = {Jinbao Zhu and Hengxuan Tang and Songze Li and Yijia Chang},
  title = {{Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation}},
  journal = {IEEE Trans. Communications},
  year = {2025},
  url = {https://openreview.net/forum?id=jld2NfBhBw},
}
Figure