Randomized Reactive Redundancy for Byzantine Fault-Tolerance in Parallelized Learning

Nirupam Gupta, Nitin H. VaidyaarXiv 2019 · arXiv

In distributed machine learning, the assumption that all participating nodes behave correctly is often violated in practice. Hardware failures, software bugs, or malicious actors can introduce "Byzantine" faults—arbitrary and potentially adversarial behavior that can prevent a model from converging.

A recent study by Nirupam Gupta and Nitin H. Vaidya, "Randomized Reactive Redundancy for Byzantine Fault-Tolerance in Parallelized Learning," introduces a novel framework designed to achieve exact fault tolerance with minimal computational overhead. By shifting from proactive to reactive redundancy, the authors demonstrate that it is possible to maintain high efficiency while guaranteeing convergence to the true optimal solution.

The Challenge of Byzantine Workers

In a standard parallelized Stochastic Gradient Descent (SGD) setup, a central Master node distributes data to multiple Workers. These workers compute gradients, which the Master then averages to update the global model parameters.

Byzantine workers disrupt this process by returning incorrect gradients. Existing defenses typically follow two paths:

  1. Robust Aggregation (Gradient Filters): These methods use statistical estimators like the geometric median to filter out outliers. While computationally cheap, they often require strong assumptions about data distribution and typically only converge to a neighborhood of the optimum, rather than the exact minimum.
  2. Coding-based Redundancy: Techniques like DRACO assign redundant data to workers to cross-check results. While they provide exact convergence, they are computationally expensive, often requiring a redundancy factor of $2f+1$ or more, which significantly reduces system throughput.

The authors aim to bridge this gap, achieving the exactness of coding-based methods with the efficiency of standard SGD.

Deterministic Reactive Redundancy

The first step in their approach is a deterministic scheme that uses fault detection rather than constant redundancy. Instead of assigning every data point to many workers upfront, the Master assigns each point to $f+1$ workers (where $f$ is the maximum number of Byzantine nodes).

If all $f+1$ workers return identical gradients, the Master accepts the result. If a discrepancy is detected, the Master triggers a "reactive" phase, assigning the same data to additional workers until a majority consensus ($2f+1$ total) can identify the correct gradient and isolate the faulty nodes.

The Deterministic Reactive Redundancy scheme triggers additional checks only when a gradient mismatch is detected.

Randomized Reactive Redundancy

To further optimize performance, the authors propose Randomized Reactive Redundancy. In this scheme, the Master does not check every iteration. Instead, it performs a fault-check with a probability $q \in (0, 1]$. In iterations where no check is performed, the Master proceeds with standard, high-speed SGD.

The Randomized Scheme introduces a probabilistic audit to maintain high computational efficiency while still catching Byzantine behavior over time.

This probabilistic approach allows the system to operate at near-peak efficiency. The authors prove that even with a small $q$, the Master will "almost surely" identify and eliminate persistent Byzantine workers as the training progresses.

Adaptive Auditing

The framework also supports an adaptive probability $q$. By monitoring the current loss function, the Master can dynamically adjust its level of "suspicion." If the loss is high or increasing, the Master increases $q$ to audit workers more frequently. As the model nears convergence and the loss decreases, $q$ can be reduced to maximize throughput.

Key Results and Insights

The paper's contributions are primarily theoretical, providing rigorous proofs for convergence and efficiency:

  • Exact Convergence: Unlike statistical filters, this method guarantees convergence to the exact global minimum $w^*$.
  • High Efficiency: The expected computational efficiency—the ratio of useful work to total computation—is $\ge 1 - q(\frac{2f}{2f+1})$. By choosing a small $q$, efficiency can be pushed arbitrarily close to 100%.
  • Fault Identification: The reactive mechanism allows the Master to permanently remove Byzantine workers from the pool once they are caught, preventing them from causing further damage.

Limitations and Future Directions

While the theoretical foundation is strong, several practical considerations remain. The current model assumes the identity of Byzantine workers is fixed and that the Master node itself is trustworthy. Additionally, the overhead of re-assigning tasks during the reactive phase in a real-world network environment needs further empirical study. Future research may look into decentralizing the auditor role and extending the framework to fully distributed settings where data cannot be easily re-shuffled between nodes.

Summary updated

Abstract

This report considers the problem of Byzantine fault-tolerance in synchronous parallelized learning that is founded on the parallelized stochastic gradient descent (parallelized-SGD) algorithm. The system comprises a master, and $n$ workers, where up to $f$ of the workers are Byzantine faulty. Byzantine workers need not follow the master's instructions correctly, and might send malicious incorrect (or faulty) information. The identity of the Byzantine workers remains fixed throughout the learning process, and is unknown a priori to the master. We propose two coding schemes, a deterministic scheme and a randomized scheme, for guaranteeing exact fault-tolerance if $2f < n$. The coding schemes use the concept of reactive redundancy for isolating Byzantine workers that eventually send faulty information. We note that the computation efficiencies of the schemes compare favorably with other (deterministic or randomized) coding schemes, for exact fault-tolerance.
BibTeX
@misc{gupta2019randomized,
  author = {Nirupam Gupta and Nitin H. Vaidya},
  title = {{Randomized Reactive Redundancy for Byzantine Fault-Tolerance in Parallelized Learning}},
  year = {2019},
  eprint = {1912.09528},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.09528},
}
Figure