Straggler Mitigation

The foundational mechanism allowing secure aggregation to proceed without waiting for all clients. Shamir Secret Sharing encodes each client's update as a polynomial, distributing shares to peers. If a client drops out, a threshold of remaining clients can reconstruct the missing mask using Lagrange interpolation, canceling it from the sum. This transforms a synchronous barrier into a fault-tolerant quorum, ensuring the server can compute the aggregate as long as a minimum number of clients respond.

A proactive technique that injects redundant computation to mask latency. The central server applies a Maximum Distance Separable (MDS) code to the computation, creating parity tasks. The server only needs results from the fastest subset of clients to reconstruct the full output. This is particularly effective for linear computations like gradient aggregation, where the sum can be recovered from a fraction of the coded results, completely eliminating the tail latency caused by the slowest nodes.

A pragmatic, non-cryptographic approach where the aggregation server sets a strict synchronization barrier with a hard deadline. Clients that fail to report within the window are simply excluded from the round. This is often paired with client selection policies that profile historical latency and reliability, oversampling faster clients to maintain a target cohort size. While simple, this introduces bias if stragglers are systematically correlated with specific data distributions.

An architectural shift that removes the global synchronization barrier entirely. The server updates the global model immediately upon receiving any client's update, using a staleness parameter to weight contributions. Techniques like FedAsync apply a mixing coefficient that decays with the age of the update. This maximizes throughput but introduces complex convergence dynamics, as the global model is constantly changing while clients train on a now-stale version of the parameters.

Reduces the communication load, a primary cause of client straggling on bandwidth-constrained devices. Techniques include:

• Sparsification: Sending only the top-k gradient components by magnitude.
• Quantization: Reducing 32-bit floats to 2-bit or 4-bit representations.
• Error Feedback: Tracking and re-injecting the residual error from compression into the next round to prevent accuracy degradation. By shrinking payloads, transmission time drops, allowing more clients to meet the aggregation deadline.

Adapts the workload to the client's capability rather than enforcing a uniform task. The server distributes variable-sized sub-models or allows clients to perform a variable number of local epochs based on their hardware profile. A powerful GPU client might train a full model for 5 epochs, while a constrained IoT sensor trains a pruned sub-model for 1 epoch. This prevents weak devices from becoming persistent stragglers by aligning the computational burden with their available resources.

While stragglers are slow or unresponsive, Byzantine nodes behave arbitrarily or maliciously. Robust systems must handle both simultaneously.

• Byzantine faults include sending contradictory or false data
• Practical Byzantine Fault Tolerance (PBFT) requires 3f+1 nodes to tolerate f faults
• In federated learning, Byzantine clients can poison the global model
• Straggler mitigation must not accidentally amplify Byzantine influence by ignoring slow-but-honest nodes

A systems-level approach where the scheduler launches redundant copies of a task when it detects a straggler, accepting the first result that completes.

• Pioneered by Google's MapReduce and Apache Hadoop
• Effective for long-tail latency in heterogeneous clusters
• Resource overhead is the primary trade-off
• Modern frameworks like Apache Spark use adaptive speculative execution that monitors task progress rates

A specialized form of coded computation designed explicitly for distributed stochastic gradient descent (SGD). It encodes gradient computations so that the parameter server can recover the exact full gradient despite stragglers.

• Replicates data blocks across workers with coding redundancy
• Each worker computes partial gradients on coded data
• The server decodes the full gradient from any sufficient subset
• Provides exact recovery, unlike approximate straggler mitigation

In federated learning, clients frequently disconnect due to network conditions or battery constraints. Dropout resilience ensures the aggregation protocol completes correctly despite these absences.

• Secure Aggregation (SecAgg) protocols use secret sharing to tolerate dropouts
• A threshold t-of-n scheme allows reconstruction when at least t clients report
• Differs from straggler mitigation by handling permanent disconnection, not just slowness
• Often combined with a synchronization barrier and timeout-based round deadlines

The all-reduce collective operation aggregates gradients across all workers. Stragglers in all-reduce block the entire synchronization barrier.

• Ring all-reduce pipelines data to hide latency but still waits for the slowest node
• Recursive doubling and Halving-Doubling algorithms reduce the impact of single-node delays
• Backup workers can be dynamically added to replace stragglers mid-operation
• Communication compression techniques like gradient quantization reduce the data volume that slow links must transmit