PaperlayerView exact revision on arXiv

Source-linked AI summary

Coded Computing for Dynamic System via Cartesian Products

Chenglin Li, Minquan Cheng, Youlong Wu

arXiv:2609.39373v4cs.ITmath.IT

TL;DR

Existing CDC schemes assume fixed worker populations, leaving arrivals and disconnections before Shuffle unaddressed. This paper combines Cartesian-product placement, Reduce reassignment, and coded delivery while preserving surviving workers’ caches and assignments. It derives exact loads for feasible disconnections and gives one-shot approximation factors of 2 with arrivals and 4 without disconnections.

  • Problem

    Existing schemes assume a fixed worker population, although workers may disconnect or become available before Shuffle, requiring abandoned Reduce functions to be reassigned.

    Source: §I · p. 1

  • Method

    The scheme uses Cartesian-product placement and delivery-aware Reduce reassignment with Communication Arrays for coded Shuffle, while preserving surviving workers’ caches and assignments.

    Source: §I · pp. 1–2

  • Results

    The scheme derives exact communication loads for feasible disconnection sets and, without disconnections, achieves approximation factors of 2 with arrivals and 4 without in the one-shot class.

    Source: §VII · p. 11

  • Takeaways & Limitations

    The scheme coordinates arriving storage and reassigned IV demands with coded delivery while retaining surviving workers’ existing caches and Reduce assignments.

    Source: §VII · p. 11

Abstract

from arXiv · show

Coded distributed computing (CDC) mitigates the Shuffle communication bottleneck through coded multicast, but existing schemes with predetermined worker populations do not directly adapt to worker arrivals and disconnections. To address these dynamics, we propose a dynamic CDC scheme that preserves surviving workers' caches and Reduce assignments while exploiting the storage brought by arriving clusters. The model accommodates general MapReduce tasks under a placement that is partly fixed and partly new. The scheme uses Cartesian products of cluster-wise placement delivery arrays (PDAs) for file placement. A delivery-aware greedy algorithm reassigns abandoned Reduce functions, and a Communication Array allows workers with no Reduce function to serve as coded transmitters. For arbitrary feasible disconnections, the scheme's exact communication load is derived. A converse bound under one-shot communication shows that, in the absence of disconnections, the scheme lies within a factor of 2 of the lower bound under these assumptions when new clusters arrive, and within a factor of 4 otherwise.

I. INTRODUCTION

Existing CDC schemes assume a fixed worker population, while dynamic MapReduce tasks can involve worker arrivals and disconnections before Shuffle. The paper jointly designs arriving-worker file placement, abandoned-Reduce reassignment, and coded delivery while preserving surviving workers’ caches and assignments.

I. INTRODUCTION

  • Worker changes before Shuffle can remove cached IVs and leave Reduce functions to reassign, while arriving workers bring storage but initially have no Reduce functions.Surviving workers’ caches and Reduce assignments remain fixed, and the participating worker set is fixed during Shuffle.Source: §I · p. 1
  • Cartesian products of cluster-wise PDAs place files at arriving workers, while delivery-aware greedy reassignment and Communication Arrays coordinate demands and coded transmissions.Workers without Reduce functions can still transmit coded messages using cached IVs.Source: §I · pp. 1–2
  • The proposed scheme significantly outperforms an extended baseline for dynamic CDC with arriving-worker file placement and Reduce reassignment.It also supports clusters with different worker counts and workers with different storage capacities.Source: §I · p. 2
  • For feasible disconnection sets, the scheme derives exact communication loads and a tight worst-case tolerance of Σ_{c∈[C]}(t_c−1) disconnected workers.Without disconnections, its approximation factors are 2 with arrivals and 4 without, relative to the best load over feasible placements in the one-shot class.Source: §I · p. 2

A. Related Work

  • Prior work covers fixed-worker CDC, elastic computation, and dynamic coded caching, but this setting couples Reduce reassignment with cache-based D2D Shuffle delivery.Unlike a server holding all files, each D2D sender must form messages from locally available IVs.Source: A. Related Work · p. 2

A. Problem Formulation

  • The model has general MapReduce output functions over input files and permits cluster sizes and cache capacities to differ.Initial workers receive distinct Reduce functions, whereas arriving workers initially receive none.Source: A. Problem Formulation · pp. 2–3

B. Preliminaries

The preliminaries define placement delivery arrays and the array properties used to construct cluster-wise placements. They also define the Cartesian product that combines arrays across clusters.

B. Preliminaries

  • A placement delivery array (PDA) is an F × K array of stars and integers satisfying column-star counts and structured conditions on repeated integers.The stated conditions require repeated symbols to occupy distinct rows and columns, with stars in the corresponding cross-positions.Source: B. Preliminaries · p. 4
  • A basic PDA adds a repeating star pattern and a map assigning each symbol an all-star row, with equal numbers of symbols assigned to each row.A PDA is g-regular when each non-star symbol occurs g times.Source: B. Preliminaries · p. 4
  • The Cartesian product of two arrays has F1F2 rows and K1+K2 columns, with rows indexed by pairs of component-array rows.Source: B. Preliminaries · p. 4

III. MAIN RESULTS

The section gives an achievable communication load for the proposed scheme under a stated feasibility condition and a one-shot converse bound. Without disconnections, it establishes a constant-factor guarantee, with the τ = 1 case optimal.

III. MAIN RESULTS

  • When at least one cluster has fewer disconnected workers than its replication level, the proposed scheme attains the achievable load given in Theorem 1.The load expression is written in terms of delivery-symbol sets across Shuffle episodes.Source: §III · p. 4
  • For any feasible placement and Reduce assignment, Theorem 2 gives a lower bound on the minimum communication load under one-shot communication.The bound uses connected file copies and requested IVs not cached by their requesting workers.Source: §III · pp. 4–5
  • Without disconnections, Theorem 3 gives a constant-factor guarantee in the one-shot class; the stated bound includes 4 when Cnew = 0, and the scheme is optimal for τ = 1.The guarantee’s constants are independent of cluster sizes, cache-ratio imbalance, and arriving replication.Source: §III · p. 5

IV. NUMERICAL RESULTS

The numerical section compares a decentralized CDC baseline with the proposed dynamic scheme across worker-arrival settings. The proposed scheme lowers average communication load in the reported comparisons, with the size of the reduction depending on the setting.

A. Decentralized CDC

  • The decentralized baseline uses random file placement and Reduce-function reassignment, with 30 random realizations per setting; its computational overhead excludes file transfer and storage I/O.Its reported operation count includes placement, reassignment and cache-pattern indexing, episode enumeration, and XOR encoding and decoding.Source: §IV · p. 5, A. Decentralized CDC · p. 5

B. Comparisons

  • Approximately 27.5%–43.4% lower average communication load across tested disconnection counts, and 2.3% at K2 = 2 versus 17.1%–20.5% for K2 ≥4, relative to the baseline.In Fig. 2(a), the higher converse is the one-shot bound with no disconnections and the general bound at the other four points; in Fig. 2(b), the one-shot bound is higher at K2 = 8 and 10.Source: B. Comparisons · pp. 5–6, Figure 2 · p. 5
  • Both schemes’ communication loads decrease as arriving-worker cache ratio increases, while the proposed scheme reduces average load by approximately 32.2%–44.8% relative to the baseline across four ratios.At M2/N = 1/5, the baseline is infeasible in 6 of 30 realizations and its average uses the remaining 24; at 3/5 and 4/5, the one-shot bound is 0.125 at both points, above proposed loads 0.167 and 0.160, respectively.Source: B. Comparisons · p. 6, Figure 3 · p. 6

V. ILLUSTRATIVE EXAMPLE

The example illustrates file placement across two clusters and shows how delivery-aware reassignment and Communication Arrays coordinate coded Shuffle transmissions. Choosing the assignment with lower simulated communication load yields a lower actual load in this example.

V. ILLUSTRATIVE EXAMPLE

  • The example has two initial workers, 12 files, two disconnected workers, and a newly arriving cluster of three workers; the clusters cache 6 and 8 files per worker, respectively.Each initial worker aims to compute a distinct output function.Source: §V · p. 6
  • The basic PDAs are combined by Cartesian product, with each row representing a file subset and each column a worker; stars indicate that the worker caches the row’s files.In this example, the rows represent individual files.Source: §V · p. 6
  • Simulated communication load is 8 when the abandoned function is assigned to k(2)1, versus 12 when assigned to k(1)1, so the example selects k(2)1.The simulation sums adjustment-round counts across episodes and tuples to choose an assignment without computing the actual load for every possible assignment.Source: §V · pp. 6–7
  • Although assigned no Reduce function, worker 2 acts as transmitter and multicasts v1,7 ⊕ v2,6 to workers k(1); the communication load is L=8/(12·2)=1/3.After worker disconnections and assignment, the non-star entries of P′ are adjusted so delivery symbols satisfy cross-star condition C3.Source: §V · p. 7

VI. GENERAL ACHIEVABLE SCHEME

The general scheme combines cluster-wise PDAs through Cartesian products to place files while preserving surviving workers’ caches. It derives delivery arrays from that placement and establishes feasibility conditions for disconnections.

2) Construction of Basic PDAs from MN PDAs:

3) Cartesian Product:

  • The Cartesian product of cluster-wise basic PDAs determines file placement, with each row assigned an equal, disjoint file batch and stars specifying which workers cache it.The number of product rows is FCart; the file count per batch must be an integer.Source: 3) Cartesian Product · p. 7
  • When a new cluster arrives, its PDA is appended to the product and each existing batch is split in file order, leaving file indices and surviving workers’ cached files unchanged.This lets each new cluster receive its allocation upon arrival.Source: 3) Cartesian Product · p. 7
  • Every file remains available exactly when at least one cluster has fewer disconnected workers than its per-file replication level; the worst-case tolerance is tight.If the total number of disconnections is below the sum of cluster replication levels, feasibility holds regardless of which clusters lose workers.Source: 3) Cartesian Product · p. 8

B. Construction of the Communication Array

The Communication Array retains the Cartesian product’s cache pattern while replacing selected non-star entries with delivery labels. Its construction supports episode-specific transmissions and ensures requested noncached batches are covered.

B. Construction of the Communication Array

  • The Cartesian product’s stars remain unchanged while its non-star entries are adjusted to form Communication Arrays for Shuffle delivery.The construction is performed for a given Reduce-function assignment vector and disconnection set.Source: B. Construction of the Communication… · p. 8
  • For each episode, the assignment vector determines which workers have Reduce demands; workers without a function in that episode have no demand.The number of Communication Arrays equals the maximum number of functions assigned to any worker.Source: B. Construction of the Communication… · p. 8
  • The construction groups eligible symbol copies across cluster blocks into merged labels, then substitutes those labels at the corresponding entries over adjustment rounds.Entries left as ◦ generate no transmission.Source: B. Construction of the Communication… · pp. 8–9
  • Every non-null Communication Array symbol satisfies the cross-star condition, and each noncached batch requested by an active worker is represented exactly once.Source: B. Construction of the Communication… · p. 9

1) From the Cartesian product to the illustrative Communication Array:

The example constructs the Communication Array by processing Cartesian-product row tuples and assigning delivery labels in rounds. The resulting array has eight labels after the six tuples are processed.

1) From the Cartesian product to the illustrative Communication Array:

  • The example divides columns into two blocks: columns 1–2 and 3–5; columns 1 and 3 have Reduce functions, column 2 is disconnected, and columns 4–5 lack demand.Product coordinates (f1, f2) map to row f = 6(f1 − 1) + f2.Source: 1) From the Cartesian product to the… · p. 9
  • For tuple d = 1, the longer block-1 list is labeled first, then the remaining copies in both blocks are labeled together.The second round includes a copy in column 4, although that column has no Reduce demand.Source: 1) From the Cartesian product to the… · p. 9
  • Tuple d = 3 has no eligible block-2 copies, so its two block-1 copies receive separate labels.The block-2 symbol occurs only in columns without demand.Source: 1) From the Cartesian product to the… · p. 9
  • Eight labels form the final Pcom after tuple rounds with counts 2, 2, 2, 1, 1, and 0.The last tuple produces no update, so the final array retains the preceding panel's entries.Source: 1) From the Cartesian product to the… · p. 9

C. Delivery-Aware Reduce Function Reassignment

The reassignment procedure compares candidate clusters using simulated communication load, while delivery processes active symbols after removing disconnected workers. The delivery cases recover missing IVs, including through transmitters with no Reduce demand.

C. Delivery-Aware Reduce Function Reassignment

  • Abandoned Reduce functions are assigned sequentially to the candidate cluster with the least simulated communication load, using the total adjustment-round count for comparison.Within a candidate cluster, assigning a function to a worker with the fewest assigned functions does not increase simulated load; the rule does not guarantee a globally optimal joint assignment.Source: C. Delivery-Aware Reduce Function… · pp. 9–10

D. Delivery

  • Delivery deletes disconnected-worker columns, then processes non-star symbols with active receivers using cases that cover the possible transmitter and demand configurations.These cases recover every requested packet, supplying active workers with their missing IVs.Source: D. Delivery · pp. 10–11
  • A connected worker with no demand can transmit when it caches all occurrence batches, allowing delivery without assigning it a Reduce function.The sender multicasts using its cached packets.Source: D. Delivery · p. 10
  • Case 3 costs ns/(ns − 1) packets per symbol when the symbol has ns active receivers.Each of the ns messages carries 1/(ns − 1) of a packet's length.Source: D. Delivery · p. 11

E. Computational Complexity

The paper gives computational-overhead bounds for constructing and running the scheme. Its conclusion derives exact communication load for feasible disconnections and approximation factors under one-shot communication without disconnections.

E. Computational Complexity

  • Placement-array construction and occurrence indexing take O(CFCartK) operations, while recording file assignments takes O(Nτ) operations.Sharing arrays and indices across episodes and recording only changes requires O(FCartK) auxiliary storage, excluding cached files and IVs.Source: E. Computational Complexity · p. 11
  • Reassignment examines at most |Dini|CUmax|R| episode-tuple combinations, and Communication Array construction uses at most U|R|maxc Vc rounds.Each construction round costs O(Kτ) operations, including transmitter selection; XOR encoding and decoding require O(NQTτ) bit operations.Source: E. Computational Complexity · p. 11

VII. CONCLUSION

  • Without disconnections, the scheme's load is within a factor of 2 of the lower bound with arrivals and a factor of 4 without arrivals.The comparison is to the minimum load over feasible placements in the stated class, under one-shot communication.Source: §VII · p. 11

APPENDIX A PROOF OF COROLLARY 1

The appendices justify special-case load bounds by counting delivery rounds and packet costs. They also prove a one-shot communication bound that remains valid after minimizing over placements.

APPENDIX A PROOF OF COROLLARY 1

  • With arrivals, every round costs one packet because a new cluster is omitted and provides a Case-1 transmitter.Normalizing the resulting ρmaxFCart packets gives the stated load expression; the same expression holds when τ = 1.Source: Appendix A · p. 11
  • Without arrivals and with τ > 1, balanced Case-3 rounds cost τ/(τ − 1) packets, and their count is at most ρminFCart.Case 2 cannot occur when every worker has one function.Source: Appendix A · p. 11
  • For one initial cluster, every round is Case 1 and the load meets Lemma 1; with at least two equal-replication clusters, the upper endpoint of (12) is attained.In the latter setting, every round merges all clusters and no all-star column exists for a merged symbol.Source: Appendix A · pp. 11–12

APPENDIX B PROOF OF THEOREM 2

  • The one-shot bound follows by weighting requested bits for each file by 1/(rc,n + 1) and summing over packets and clusters.The proof applies the bound for every cluster before dividing by NK0T and taking the maximum over clusters.Source: Appendix B · p. 12
  • Substitution proves (17), which remains valid after minimizing over placements because its right-hand side is independent of M.Source: Appendix B · p. 12

APPENDIX C PROOF OF THEOREM 3

The proof bounds the scheme’s gap to a one-shot converse, establishes when all files retain surviving copies, verifies the Cartesian-product array construction, and proves a submodularity property used in the greedy analysis.

APPENDIX C PROOF OF THEOREM 3

  • With arrivals, the scheme’s ratio to the converse is at most 2, and without arrivals the two comparison factors are each at most 2; the arrival bound is tight.For the stated example, the optimum load is 1/4 and the scheme’s load is 1/2.Source: Appendix C · p. 12

APPENDIX D PROOF OF PROPOSITION 1

  • All files have a surviving copy exactly when δc < tc for some cluster c; disconnecting the τ workers caching one batch removes all its copies, showing the condition is tight.Each batch has at least max{tc − δc, 0} surviving copies in cluster c.Source: Appendix D · p. 12

APPENDIX E PROOF OF PROPOSITION 2

  • The Cartesian-product construction preserves the cross-star condition across blocks, and its copy lists label every requested position exactly once.Copies omitted from the construction have no active receiver.Source: Appendix E · pp. 12–13

APPENDIX F PROOF OF PROPOSITION 3

  • For a fixed r, adding a worker has zero marginal cost when its cluster is represented or it lies outside K⋆c(rc); otherwise the cost is the positive part of Vc minus the largest represented weight.Because this marginal cost cannot increase as the active set grows, G is monotone and submodular.Source: Appendix F · p. 13
Loading 2609.39373v4…