Coded Federated Computing in Wireless Networks with Straggling Devices and Imperfect CSI

Sukjong Ha, Jingjing Zhang, Osvaldo Simeone, Joonhyuk KangarXiv 2019 · arXiv

Abstract

Distributed computing in wireless environments faces a "double whammy" of bottlenecks: slow computing nodes, known as stragglers, and unreliable communication due to interference and imperfect channel knowledge. This paper introduces a framework for Coded Federated Computing that addresses these challenges by combining Lagrange coding with a novel superposition-based data shuffling strategy. Through numerical simulations, we demonstrate how this approach significantly reduces total latency in distributed tasks like federated learning by optimizing the trade-off between computation and communication phases.

Introduction

While traditional distributed computing assumes high-speed, reliable wired connections, emerging paradigms like wireless data centers and federated learning operate in much more volatile environments. In these setups, two primary issues hinder performance:

  1. Stragglers: Hardware variations or background tasks can cause some devices to be significantly slower than others, creating a bottleneck if the system must wait for every node to finish.
  2. Wireless Impairments: Shared wireless channels suffer from interference. Furthermore, the network controller often possesses Imperfect Channel State Information (CSI), making it difficult to optimize data transmissions during the critical "Shuffle" phase of the Map-Reduce process.
System model for coded federated computing in a wireless network, featuring a network controller and distributed devices.

Methodology

The proposed framework utilizes a Map-Shuffle-Reduce architecture enhanced by a concatenated coding approach to minimize total latency—the sum of time spent on computation (Map phase) and data movement (Shuffle phase).

Coding for Resilience and Redundancy

To handle stragglers, the system employs Lagrange Coded Computing. This allows the recovery of the final result of a multivariate polynomial function from any subset of devices that exceeds a specific recovery threshold, eliminating the need to wait for the slowest nodes. This is followed by Repetition Coding, which strategically replicates data across devices. This redundancy is not just for fault tolerance; it creates opportunities for more efficient communication during the shuffle phase.

The concatenated coding scheme (a) showing Lagrange and repetition coding, and the impact of a straggler on the communication topology (b).

Robust Shuffling Strategies

The paper evaluates three strategies for moving data between devices:

  • Coded Multicasting: Employs XOR operations to deliver data useful to multiple devices in a single transmission.
  • One-Shot Linear Precoding (Zero-Forcing): Uses beamforming to cancel interference, allowing simultaneous transmissions, though it requires accurate CSI.
  • Superposition Coding: This is the paper's core innovation. It layers a multicasting signal atop a precoded signal. This hybrid approach is designed to be robust; it exploits known channel characteristics via precoding while using multicasting to hedge against the uncertainty of imperfect CSI.

Key Insights and Results

Numerical simulations involving 30 distributed devices computing polynomial functions revealed several critical insights:

  • The Optimal Wait: There exists a "Goldilocks" number of devices to wait for. Waiting for too many nodes triggers the straggler bottleneck, while waiting for too few increases the communication load during the shuffle phase.
  • Superposition Dominance: Superposition coding consistently achieved the lowest total latency. When CSI quality is high, it matches the performance of linear precoding; when CSI is poor, it gracefully degrades to the performance of multicasting, whereas pure precoding fails significantly.
  • Communication-Computation Trade-off: Increasing computational redundancy through coding reduces the "communication load," enabling higher multicast gains and lower shuffle-phase latency.

Conclusion and Future Work

This research demonstrates that integrated coding strategies can effectively mitigate the physical and computational uncertainties of wireless federated computing. While the current model assumes full-duplex capabilities and high Signal-to-Noise Ratios (SNR), future work will explore half-duplex constraints and the application of these techniques to non-polynomial functions and heterogeneous device clusters.

Summary updated

BibTeX
@misc{ha2019coded,
  author = {Sukjong Ha and Jingjing Zhang and Osvaldo Simeone and Joonhyuk Kang},
  title = {{Coded Federated Computing in Wireless Networks with Straggling Devices and Imperfect CSI}},
  year = {2019},
  eprint = {1901.05239},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1901.05239},
}
Figure