Coding for Distributed Fog Computing

Songze Li, Mohammad Ali Maddah-Ali, Amir Salman Avestimehr

Introduction

Fog computing shifts data processing from centralized cloud datacenters to the network edge—utilizing devices like smart cars, routers, and base stations. While this proximity reduces physical distance, it introduces two primary challenges: communication bottlenecks due to limited edge bandwidth and stragglers, where unpredictable node performance delays entire distributed tasks. Traditional "uncoded" distributed computing, such as standard MapReduce, fails to exploit the inherent redundancy available in Fog networks to mitigate these issues.

Coding Strategies for Fog Computing

The researchers propose three primary coding-based strategies to optimize performance by trading redundant computation for improved network efficiency.

Minimum Bandwidth Codes (MBC)

MBC creates an inverse-linear tradeoff between computation and communication. By performing redundant mapping (processing the same data at multiple nodes), the system enables "coded multicast" opportunities. Instead of individual transmissions, nodes can XOR multiple results into a single broadcast packet that satisfies several neighbors simultaneously. As shown in the figure below, MBC significantly reduces the communication load compared to uncoded schemes as the computation load increases.

The inverse-linear tradeoff between computation load (r) and communication load (L) achieved by Minimum Bandwidth Codes.

Minimum Latency Codes (MLC)

MLC utilizes Maximum Distance-Separable (MDS) erasure codes to handle stragglers. By encoding a task into $n$ parts where only $k$ results are needed ($n > k$), the system can ignore the slowest nodes. This shifts the paradigm from waiting for the entire network to waiting only for the fastest subset of nodes.

Unified Coding Framework

The paper's most significant contribution is a unified framework that combines MBC and MLC. This allows system designers to select an optimal operating point on a curve that balances communication load against computation latency, adapting to real-time network conditions.

The Unified Coded Framework provides a Pareto-optimal curve between communication load and computation latency.

Experimental Evaluation

The framework was evaluated using core computational benchmarks:

  • TeraSort: In experiments with 12 GB of data across 16 Amazon EC2 instances, CodedTeraSort ($r=5$) reduced data shuffling time by 4.24x. Despite the overhead of redundant mapping, the total job response time improved by 3.39x.
  • Matrix Multiplication: In a simulated 18-node network, the unified framework achieved a 38.4% performance gain over MBC alone and a 29.3% gain over MLC alone.

Conclusion

This research demonstrates that redundancy is a valuable resource in Fog computing. By strategically "wasting" CPU cycles on redundant tasks, systems can significantly reduce network congestion and total latency. Future work will focus on addressing node heterogeneity, complex network topologies, and the security challenges of verifiable computing in decentralized environments.

Summary updated

BibTeX
@article{li2017coding,
  author = {Songze Li and Mohammad Ali Maddah-Ali and Amir Salman Avestimehr},
  title = {{Coding for Distributed Fog Computing}},
  journal = {IEEE Communications Magazine},
  year = {2017},
  url = {https://openreview.net/forum?id=ti6DDKzAYQ5},
}
Figure