Source-linked AI summary
Coding for Distributed Fog Computing
Songze Li, Mohammad Ali Maddah-Ali, A. Salman Avestimehr
TL;DR
Fog networks have abundant, growing edge redundancy that coding can leverage to reduce communication load and computation latency. The paper reviews Minimum Bandwidth Codes and Minimum Latency Codes, and discusses a unified tradeoff framework for optimizing system performance.
Problem
Fog networks have abundant edge resources, and the paper examines how coding can leverage them to reduce communication bandwidth consumption and computation latency.
Source: §II · p. 1Method
The paper reviews Minimum Bandwidth Codes and Minimum Latency Codes and discusses a unified framework that trades computation latency against communication load.
Source: §II · p. 1Results
Coding is demonstrated as a way to leverage Fog redundancy to substantially reduce bandwidth consumption and computation latency.
Source: §VI · p. 6Takeaways & Limitations
The unified framework lets Fog systems choose a point on the computation-latency and communication-load tradeoff to optimize performance.
Source: §VI · p. 6
Abstract
from arXiv · showhide
Redundancy is abundant in Fog networks (i.e., many computing and storage points) and grows linearly with network size. We demonstrate the transformational role of coding in Fog computing for leveraging such redundancy to substantially reduce the bandwidth consumption and latency of computing. In particular, we discuss two recently proposed coding concepts, namely Minimum Bandwidth Codes and Minimum Latency Codes, and illustrate their impacts in Fog computing. We also review a unified coding framework that includes the above two coding techniques as special cases, and enables a tradeoff between computation latency and communication load to optimize system performance. At the end, we will discuss several open problems and future research directions.
II. INTRODUCTION
Fog computing pools edge resources near users, and this paper surveys coding schemes that exchange abundant computation for reduced communication load and computation latency. It also discusses a unified tradeoff framework and future research directions.
II. INTRODUCTION
- Fog moves service provision closer to end users by pooling resources such as smartphones, cars, base stations, and routers at the network edge.The architecture is presented as a way to meet emerging IoT service requirements.Source: §II · p. 1
- Coding leverages underused edge computation to reduce communication bandwidth and computation latency in Fog applications.These resource reductions are particularly important in Fog computing.Source: §II · p. 1
- Minimum Bandwidth Codes trade an r-fold increase in computation load for an r-fold reduction in communication load.They do so by evaluating each computation at r carefully chosen nodes.Source: §II · p. 1
- Minimum Latency Codes use redundant computation to alleviate stragglers, trading increased computation load for reduced overall job response time.Their speedup is proportional to the amount of injected redundancy.Source: §II · p. 1
- Fog redundancy grows linearly with network size, while communication bottlenecks and stragglers are more severe than in Cloud computing.The paper closes by highlighting open problems and future research directions.Source: §II · pp. 1–2
- A unified framework combines the two coding concepts through a tradeoff between computation latency and communication load.It allows a Fog system to operate at any point on that tradeoff.Source: §II · p. 1
III. MINIMUM BANDWIDTH CODES
Minimum Bandwidth Codes use repeated mapping and coded multicast to exchange more computation at the edge for less communication. The section illustrates bandwidth and response-time reductions in Fog workloads, including sorting and mobile computing.
III. MINIMUM BANDWIDTH CODES
- For MapReduce-style workloads, edge nodes Map distributed input files into intermediate values, then Reduce those values into output functions.The motivating examples include distributed map or traffic data and dataset repositories.Source: §III · p. 2
- With r = 2, the three-node example uses communication load 3, a 4× gain over no computation redundancy and a 2× gain over uncoded shuffling.Each file is mapped on two ENs, and each EN multicasts an XOR useful to the other two.Source: §III · pp. 2–3, Figure 2 · p. 2
- Communication load falls by a factor equal to computation load r when r times more subtasks are computed than without redundancy.This is the general comparison with conventional uncoded strategies.Source: §III · p. 3
- The scheme repeats each data block across r nodes in a specific pattern, enabling coded multicast messages that deliver useful data simultaneously to r or more nodes.For r = 2, the section reports more than 50% lower overall communication load when each Map task is repeated at one other node.Source: §III · p. 3
- The coded-multicast idea extends opportunities from caching and wireless D2D delivery to data shuffling in distributed computing.The section presents this extension as a way to reduce required communication load.Source: §III · p. 3
- For applications where data movement takes 10×–100× task-computation time, Minimum Bandwidth Codes can reduce overall job response time by approximately 1.5–5×.Source: §III · p. 3
- CodedTeraSort reduced overall job response time by 3.39×, while reducing data-shuffling time by 4.24× despite 5.83× more Map task computation.The reported job sorted 12 GB over 16 EC2 instances; Table I summarizes its average response times.Source: §III · p. 3, Table I · p. 4
- In the mobile platform, the normalized bandwidth consumption is 1/μ − 1, reducing uncoded communication load K(1 − μ) by a factor of μK.Because bandwidth consumption is independent of user count K, the platform can serve an unlimited number of users with constant communication load.Source: §III · pp. 3–4
IV. MINIMUM LATENCY CODES
Minimum Latency Codes use redundant coded tasks so a Fog client can complete a job without waiting for every edge node. The section reports lower response times and greater tolerance of missing task results, with performance estimates conditioned on the stated setting.
IV. MINIMUM LATENCY CODES
- The motivating applications distribute a dataset across edge nodes, which process a client’s input and return intermediate results for the client to reduce.The section identifies distributed machine-learning algorithms, including gradient descent for linear regression, as examples.Source: §IV · p. 4
- In the matrix-multiplication example, the client decodes AX after results arrive from EN 1 and EN 3, leaving straggling EN 2 out of the runtime.The coded tasks are A1X, A2X, and (A1 + A2)X; any two task results recover the final result.Source: §IV · p. 4, Figure 4 · p. 4
- The uncoded matrix-multiplication approach needs results from all three ENs, so one slow or disconnected node can delay completion substantially or prevent it.It divides the data matrix evenly among the three nodes and concatenates their returned matrices.Source: §IV · p. 4
- The code decomposes a job into k tasks, encodes them as n MDS-coded tasks, and assigns one to each node; the fastest k results suffice.The “any k of n” property means slow-node tasks need not be awaited.Source: §IV · pp. 4–5
- For a shifted-exponential distribution, Minimum Latency Codes reduce response time by Θ(log n); reported gains include 2.3×–4.6× speedup for 10–100 nodes and a 35.7% average reduction in an Amazon EC2 gradient-descent experiment.The section anticipates larger gains in more heterogeneous Fog environments, but presents that as an expectation.Source: §IV · p. 5
- An (n, k) Minimum Latency Code guarantees successful computation from any k returned task results, unlike uncoded execution or repetition codes.This provides survivability when nodes fail or disconnect and their results never return.Source: §IV · p. 5
V. A UNIFIED CODING FRAMEWORK
The unified coding framework trades Map-phase computation latency against Shuffle-phase communication load, with Minimum Bandwidth Codes and Minimum Latency Codes as its extremes. By selecting an operating point, it can minimize total response time and adapt the balance to network conditions.
V. A UNIFIED CODING FRAMEWORK
- 186s is the unified framework's minimum total response time, versus 302s for Minimum Bandwidth Codes and 263s for Minimum Latency Codes.For the 18-node matrix multiplication example, this uses the fastest 12 nodes to finish their Map tasks.Source: Figure 5 · p. 5, §V · p. 5
- The framework approximately exhibits an inverse-linear relationship between Map computation latency and Shuffle communication load, with the two earlier codes at opposite extremes.Minimum Bandwidth Codes minimize communication load, while Minimum Latency Codes minimize computation latency.Source: §V · p. 5
- MDS-coded Map tasks are assigned repetitively to edge nodes; after enough nodes finish, coded multicast opportunities serve the remaining data demands.In the example, 30 coded tasks are assigned to pairs of nodes, allowing the Map phase to end when the fastest four of six nodes finish.Source: §V · pp. 5–6
- The operating point can shift with network conditions: wait for more Map results on slow networks, or finish Map earlier when nodes are slow or unresponsive.Waiting for more nodes creates better multicast opportunities, while earlier termination shifts load to the network.Source: §V · p. 6
VI. CONCLUSIONS AND FUTURE RESEARCH DIRECTIONS
The conclusion reiterates that coding leverages abundant edge computation to reduce bandwidth use and computation latency, and that a unified framework spans a tradeoff between them. It identifies future research directions for extending these ideas to more realistic Fog settings.
Heterogeneous computing nodes
- Heterogeneous Fog nodes have different processing and storage capacities; practical task assignment and coding with provable near-optimality remain open problems.Splitting powerful nodes into homogeneous virtual nodes is offered as a simple heuristic.Source: §VI · p. 6
Networks with multi-layer and structured topology
- Current distributed-computing code designs assume processing nodes share one link, so they need extension to multilayer topologies with switches and links of different capacities.Source: §VI · p. 6
Multi-stage computation tasks
- For DAG-based jobs, locally applying codes stage by stage is possible, but globally designing codes around interactions between consecutive stages is expected to reduce bandwidth and response time further.Source: §VI · p. 6
Coded computing overhead
- The current Fog model does not adequately account for encoding and decoding, multicast communication, or maintaining data redundancy across nodes.A comprehensive overhead model is identified as important for making the analysis more relevant to practical Fog systems.Source: §VI · p. 6
Verifiable distributed computing
- Fog offloads work from weaker clients to stronger edge nodes, creating a need for verifiable computing; codes may use computation redundancy more efficiently to verify results.Source: §VI · p. 6
Exploiting the algebraic structures of computation tasks
- Minimum Bandwidth Codes apply to general MapReduce tasks, while Minimum Latency Codes are limited to particular linear functions such as matrix multiplication.The paper identifies extending Minimum Latency Codes to a broader task class as an open direction.Source: §VI · p. 6
Communication-heavy applications
- Minimum Bandwidth Codes are envisioned to support many Fog nodes under bounded communication load, motivating tests on whether communication-heavy tasks can run over distributed Fog networks.Source: §VI · p. 6
Plug-and-Play Fog nodes
- Designing codes that preserve computation integrity while Fog nodes join or leave asynchronously remains an open research direction.The envisioned software package would be installed and maintained distributively on each Fog node.Source: §VI · p. 6