PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Coding Framework for Distributed Computing with Straggling Servers

Songze Li, Mohammad Ali Maddah-Ali, A. Salman Avestimehr

arXiv:1609.01690v1cs.ITcs.DC

TL;DR

Distributed computing with straggling servers must balance computation latency against communication load under storage constraints. The paper proposes a unified coded framework that integrates repetition-based coded multicasting and MDS-based redundant computation, permitting systematic operation across this tradeoff. It also proves a lower bound and shows constant-factor proximity at the tradeoff endpoints.

  • Problem

    The paper addresses how to trade computation latency against communication load when distributed linear computations use storage-limited servers subject to stragglers.

  • Method

    The paper unifies repetitive coded multicasting and MDS-based redundant computation in a framework that operates across the latency-load tradeoff.

  • Results

    At minimum latency, the proposed scheme achieves 1.33× the minimum communication load, while at maximum latency it achieves 2.67× the lower bound.

  • Takeaways & Limitations

    The framework provides systematic latency-load operating points and places the endpoint schemes within one coded design.

Abstract

from arXiv · show

We propose a unified coded framework for distributed computing with straggling servers, by introducing a tradeoff between "latency of computation" and "load of communication" for some linear computation tasks. We show that the coded scheme of [1]-[3] that repeats the intermediate computations to create coded multicasting opportunities to reduce communication load, and the coded scheme of [4], [5] that generates redundant intermediate computations to combat against straggling servers can be viewed as special instances of the proposed framework, by considering two extremes of this tradeoff: minimizing either the load of communication or the latency of computation individually. Furthermore, the latency-load tradeoff achieved by the proposed coded framework allows to systematically operate at any point on that tradeoff to perform distributed computing tasks. We also prove an information-theoretic lower bound on the latency-load tradeoff, which is shown to be within a constant multiplicative gap from the achieved tradeoff at the two end points.

I. INTRODUCTION

The paper unifies coding strategies for distributed computing with straggling servers by formalizing a tradeoff between computation latency and communication load. Its framework includes prior minimum-bandwidth and minimum-latency schemes as endpoints, supports intermediate operating points, and has an information-theoretic lower bound that is tight within a constant factor at the endpoints.

  • Motivation: Prior work uses repetitive computations for coded multicasting to reduce shuffling time, or MDS codes to reduce computation latency under straggling.The first approach targets communication, while the second targets the computation phase.
  • Framework: The unified coded framework treats the prior schemes as extreme points that individually minimize communication load or computation latency.The framework integrates both coding techniques rather than selecting only one endpoint.
  • Framework: The proposed scheme allows distributed computing tasks to operate systematically at any point on the latency-load tradeoff.The tradeoff is illustrated for a matrix multiplication job with N = 840 output vectors, K = 14 servers, and µ = 1/2.
  • Guarantees: An information-theoretic lower bound on communication load for a given computation latency is within a constant multiplicative factor of the scheme at both endpoints.The bound is obtained using concatenated problem instances and cut-set bounds on server subsets.
  • Problem formulation: The paper fixes storage-determined computation load and studies the tradeoff between Map computation latency and Shuffle communication load.This extends the tradeoff considered in [1] by introducing computation latency as a second axis.

A. System Model

The system model distributes matrix multiplication across storage-limited servers that may store encoded rows of the matrix. Each server's storage encoding is chosen before computation and can instantiate either repetition-based or MDS-based storage.

  • Problem: The task is to compute N output vectors y_j = Ax_j from a matrix A and input vectors x_j.The computation is distributed because the full matrix cannot be assumed to fit at one server.
  • Storage model: Each of K servers stores enough information for a µ fraction of A's entries, with the collective storage sufficient to recover the entire matrix.The local memory size is µmnT bits under the stated model.
  • Storage model: Servers may use linear encoding matrices E_k to store coded rows U_k = E_kA.The encoding matrices are design parameters selected during the prior storage-design stage.
  • Special cases: The Minimum Bandwidth Code stores selected rows of A according to a repetition pattern, whereas the Minimum Latency Code stores random linear combinations forming an MDS code.These are two distinct storage designs represented within the general encoding formulation.

B. Distributed Computing Model

The distributed computation uses Map, Shuffle, and Reduce phases, with latency determined by when a sufficient server subset finishes Map computations and load determined by multicast communication. Redundant Map results may be retained when they reduce subsequent communication.

  • Map Phase: During Map, each server computes coded intermediate vectors from its locally stored matrix and every input vector.For each input x_j, the intermediate result is z_{j,k} = U_kx_j = E_ky_j.
  • Map Phase: The Map phase stops when a subset Q of servers finishes and can collectively provide enough intermediate vectors to reconstruct all outputs.The subset may include redundant computations if those results lower communication in later phases.
  • Map Phase: The Minimum Bandwidth Code waits for all servers, while the Minimum Latency Code waits for the fastest ⌈1/µ⌉ servers.These choices represent opposite strategies for selecting the Map-completed server set.
  • Reduce Phase: Computation latency D is the average Map-phase time, after which outputs are assigned uniformly across the servers in Q.Each server in Q receives a disjoint set of N/|Q| output vectors.
  • Shuffle Phase: In Shuffle, each server multicasts an encoded message of its local intermediate values so every server can recover its assigned outputs.Communication load L is the normalized average total size of these messages.

C. Illustrating Example

The example contrasts repetition-based minimum-bandwidth coding with MDS-based minimum-latency coding. The former spends more Map time to halve communication load, while the latter finishes Map earlier at higher Shuffle load.

  • Setup: The example uses m = 12 matrix rows, N = 4 input vectors, K = 4 servers, and storage size µ = 1/2.The server Map latencies follow a shifted-exponential model.
  • Minimum Bandwidth Code: The Minimum Bandwidth Code repeats each row across µK = 2 servers, enabling coded multicast messages with coding gain µK.The repeated Map computations create side information that lets servers cancel interfering values.
  • Minimum Bandwidth Code: The Minimum Bandwidth Code waits for all four servers and uses three XOR messages per server to exchange needed intermediate values.Its communication load is half that of the Minimum Latency Code in the comparison.
  • Minimum Latency Code: The Minimum Latency Code uses random linear combinations whose 24 coded rows form a (24, 12) MDS code.Any 12 coded intermediate values suffice to recover an output vector, so the fastest two servers can terminate Map.
  • Minimum Latency Code: The Minimum Latency Code achieves computation latency D(2)=19/6 and communication load L=2 in the example.The two fastest servers continue the Reduce phase and unicast the intermediate values needed by one another.
  • Comparison: The Minimum Bandwidth Code uses about twice the Map time of the Minimum Latency Code while achieving half its communication load.Together, the schemes illustrate the two endpoints of the latency-load tradeoff.

III. MAIN RESULTS

The paper characterizes achievable latency-load pairs through a unified coded framework and an information-theoretic outer bound. The scheme interpolates between minimum-latency and minimum-bandwidth designs, with constant-factor gaps at the endpoints and a bounded intermediate gap in the evaluated setting.

  • Achievable region: The latency-load region contains the lower convex envelope of achievable points generated by the unified coded framework.The framework jointly designs storage and shuffling for different numbers q of servers completing Map computations.
  • Endpoint schemes: The Minimum Latency Code and Minimum Bandwidth Code correspond to the two extreme operating points of the framework.The former minimizes computation latency, while the latter minimizes communication load.
  • Tradeoff evaluation: The achieved latency-load pairs approximately follow an inverse-linear relationship between latency and communication load in the evaluated setting.For N = 180 output vectors, K = 18 servers, and µ = 1/3, increasing latency from 120 to 240 reduces load from 43 to 23, a factor of 1.87.
  • Endpoint guarantees: At minimum latency, the proposed scheme is within a factor of 2 of the information-theoretic lower bound.For q = 1/µ, the scheme achieves L(1/µ) = N(1 − µ).
  • Endpoint guarantees: At maximum latency, the proposed scheme is within a factor of 3 + 5/µK of the lower bound, with a 2.67× gap when K = 18 and µ = 1/3.Here q = K and the scheme corresponds to the Minimum Bandwidth Code.
  • Outer bound: For intermediate latency from 70 to 270, the evaluated communication load is within at most 4.2× of the lower bound, while complete characterization remains open.The lower bound applies to any storage design and data-shuffling scheme.

IV. PROPOSED CODED FRAMEWORK

The proposed framework combines MDS-coded storage with repeated Map computations and coded shuffling. In the example, four completed servers support reduction through multicast exchanges followed by uncoded transmission of residual demands.

  • Storage Design: The framework first generates MDS-coded rows and stores each coded-row batch across a specific subset of servers.In the example, 30 coded rows are partitioned into 15 batches of size 2, each stored at a unique server pair.
  • Coded Shuffle: Coded shuffling groups servers into subsets and multicasts intermediate values that are simultaneously useful to multiple recipients.Figure 5 illustrates multicast across Servers 1, 2, and 3, with analogous communication for three other subsets.
  • Coded Shuffle: Each server recovers 18 needed intermediate values through coded multicasting, then receives 12 additional values by unicast to complete its reductions.Across four servers, the residual uncoded transmission consists of 48 intermediate values.

B. General Scheme

The general scheme combines MDS-coded storage, straggler-resilient Map execution, and coded shuffling to achieve latency-load operating points. Its construction partitions coded rows across server subsets, waits for the fastest q servers, and selects the lower-load continuation of shuffling.

  • Storage Design: The scheme uses an MDS code to encode the rows of matrix A, then partitions the coded rows into batches indexed by server subsets.Each batch is stored by the servers in its associated subset.
  • Storage Design: Each server stores a batch when it belongs to that batch’s µq-sized label subset, creating replicated coded-row storage across the K servers.The storage assignment is determined before computation.
  • Map Phase Execution: The Map phase waits for the fastest q servers, whose collectively stored coded rows suffice to support the subsequent Reduce computations.Every possible q-server completion set must collectively contain enough distinct coded rows.
  • Coded Shuffle: Servers in the completing set Q multicast XOR-coded packets that can be useful to multiple recipients, exploiting intermediate values already known locally.The greedy scheme prioritizes multicast packets simultaneously useful for the largest number of servers.
  • Coded Shuffle: The shuffle continues over increasing subset sizes until each reducing server receives enough intermediate values; the smallest sufficient size is j = s_q + 1.This stopping condition supplies the required intermediate values for reduction.
  • Communication Load: The final communication load is the smaller of the uncoded-completion load L1 and the coded-continuation load L2.Memory sharing across achieved pairs yields their lower convex envelope.

V. CONVERSE

The converse derives an information-theoretic outer bound on the latency-load region using compound output assignments and cut-set bounds. Averaging over possible Map stopping points yields the lower convex envelope of per-latency outer-bound pairs.

  • Outer-bound construction: The converse constructs an outer bound on the latency-load region by analyzing schemes that stop Map computation after q servers finish.For such schemes, the computation latency is the expected qth order statistic of the Map computation times.
  • Compound assignments: The output vectors are partitioned into q groups and assigned to servers, then multiple circularly shifted assignments are considered for the cut-set argument.The assignments use shifts with step size t, producing a compound setting across multiple output assignments.
  • Assignment symmetry: Because each server multiplies all input vectors by the same stored matrix, relabeling output vectors makes the minimum communication load identical across the considered assignments.This invariance allows the cut-set bounds from the compound setting to be combined.
  • Cut-set bounds: The first t servers must recover all output vectors from their local results and received messages, yielding cut-set bounds for subsets of servers.The argument also considers q cyclic subsets of size t and sums the resulting bounds.
  • Latency-load region: For randomized stopping points, the communication load is lower bounded by the same convex combination of the bounds associated with each possible q.Considering all distributions of q gives the lower convex envelope of {(E{S(q)}, ¯L(q)) : q = ⌈1/µ⌉, . . . , K} as an outer bound.

APPENDIX

The appendix proves that at maximum latency, when all K servers complete Map computation, the proposed scheme is within a constant multiplicative factor of the communication-load lower bound. The proof handles parameter ranges separately and compares the resulting bounds.

  • Maximum-latency endpoint: At maximum latency, the proposed coded scheme, including the Minimum Bandwidth Code, is within a constant multiplicative factor of the communication-load lower bound.This setting has all K servers complete their Map computations.
  • Proof structure: The proof assumes µK is an integer and uses the expressions L(K) and ¯L(K) from the main analysis.The appendix bounds the relevant expression in two cases before completing the comparison.
  • Proof conclusion: Comparing the two case-specific bounds completes the constant-gap proof.The argument concludes by comparing equations (26) and (30).
Loading 1609.01690v1…