Pith. sign in

REVIEW 2 major objections 5 minor 16 references

Heterogeneous Coded Distributed Computing: Joint Design of File Allocation and Function Assignment

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Unequal node speeds need not inflate MapReduce shuffle load: joint file allocation and function assignment keeps communication within a constant factor of the homogeneous optimum.

desk verdict Real achievable scheme for heterogeneous MapReduce, but the constant-gap proof for low average load rests on an unstated entropy assumption that makes Lemma 1 false as written. read the letter →

arxiv 1908.06715 v1 pith:PELDTRCW submitted 2019-08-19 cs.IT math.IT

Fan Xu , Meixia Tao This is my paper · ORCID
classification cs.ITmath.IT MSC 68M1468P2094A15
keywords codeddistributedcomputingMapReduceheterogeneouscomputationloadfileallocationfunctionassignmentcommunication-computationtradeoffmulticastingconstantmultiplicativegap
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether heterogeneity in node computing power forces a larger communication cost in MapReduce-style distributed computing, and answers no: for any vector of computation loads, it constructs a file allocation and a function assignment whose shuffle load stays within a constant multiplicative factor of the optimal load in a homogeneous system with the same average computation load. The construction first partitions input files into disjoint compulsory batches, then lets nodes with spare capacity compute optional files from other batches; the overlap creates coded multicast opportunities in the shuffle phase. Two assignment rules are proposed: computation-aware, which sets each node's share of output functions proportional to its computation load, and shuffle-aware, which assigns all output functions to high-load nodes so that multicast messages need no padding. The constant gap is at most 115, and in the high-load regime the shuffle-aware rule can even beat the homogeneous optimum. A sympathetic reader would take the contribution as a design recipe: file allocation and function assignment should be chosen jointly, and the proof shows the recipe is within a universal constant of optimal.

What carries the argument

The load-bearing object is the surplus computation ratio $P_k=(m_k-l_k)/(1-l_k)$, where $l_k$ is the fraction of files in node $k$'s compulsory batch. The first step of the allocation fills nodes as equally as possible until low-load nodes are exhausted; the second step treats every remaining node's batch like a decentralized cache and gives each other node a product-measured share, making sub-batch $N_k^{\Psi}$ available to exactly the node set $\Psi$. This product structure turns the shuffle phase into coded multicasting: a message sent to node set $\Psi$ costs $l_k \prod_{j\in\Psi}P_j \prod_{j\notin\Psi}(1-P_j) \max_{i\in\Psi} w_i(1-P_i)/P_i$, with zero-padding to equalize the per-node streams. Ordering high-load nodes by $w_i(1-P_i)/P_i$ collapses the sum over all subsets into the closed form of Theorem 1. For the constant-gap result, the companion machinery is the cut-set lower bound of Lemma 1, which says any node subset $T$ must receive at least $(1-\sum_{k\in T}m_k)\sum_{k\in T}w_k\,QNT$ bits; the two assignments are chosen so that the terms in the achievable load can be bounded against this quantity piece by piece.

What would settle it

Numerically enumerate all computation-load vectors for $K=4$ with average load $\bar m<0.55$, compute $L_A$ from Theorem 2 and $L^*_{\mathrm{Hom}}$, and test whether the maximum ratio exceeds 115; any such instance would refute Corollary 1. For the lower bound itself, instantiate a system where all files are identical or where Map outputs are highly correlated and check whether the optimal shuffle load falls below the cut-set expression (23), which would break Lemma 1.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes a closed-form achievable communication load $L_A(m,w)$ for a $K$-node heterogeneous MapReduce system with computation-load vector $m$ and function-assignment vector $w$ (Theorem 1), and then shows that two concrete assignments make $L_A$ comparable to the homogeneous benchmark. With the computation-aware assignment $w_k\propto m_k$, the gap to the optimal homogeneous load $L^*_{\mathrm{Hom}}(\bar m)$ is below 115 whenever the average load is below 0.55; with the shuffle-aware assignment, which concentrates all output functions on the high-computation nodes and equalizes $w_k(1-P_k)/P_k$, the same gap holds when the average load is at least 0.55 (Corollary 1). The proof isolates the gap into two pieces: the achievable load against a cut-set lower bound for the same $(m,w)$, and that lower bound against the homogeneous optimal load. This is an extension rather than a new fundamental limit: the paper gives a constructive upper bound and a lower bound that matches within a constant, not an exact characterization of the heterogeneous tradeoff.

Load-bearing premise

The constant-gap proof rests on assuming the intermediate values $v_{q,n}$ for distinct files and functions are independent, uniform, full-entropy $T$-bit strings (Appendix B, eq. (23)), an assumption the system model never states; the integrality assumptions on $N$ and $Q$ are additional unquantified premises.

Editorial extensions

If this is right

  • For average computation load below 0.55, computation-aware function assignment alone suffices to keep shuffle load within a factor of 115 of the homogeneous optimum.
  • For average load at least 0.55, shuffle-aware assignment keeps the same constant gap and, in some regimes, yields a strictly smaller load than the homogeneous optimal load $L^*_{\mathrm{Hom}}$.
  • The closed-form load formula applies to any function assignment, so other assignments can be plugged in and evaluated directly rather than re-deriving the whole scheme.
  • The scheme needs the number of input files and output functions to be large enough that all sub-batch sizes and function counts are integers; the paper gives scaling factors but does not quantify the rounding penalty when $N$ or $Q$ fall short.
  • The proof's lower bound is generic: any scheme with the same cut-set bound and load formula inherits the constant-gap statement.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper does not pursue it, but the same two-step 'compulsory plus optional' allocation template should transfer to other resource dimensions such as storage capacity or communication budget, with the same product-form overlap generating coded-multicast gains.
  • The constant 115 is a proof artifact of the appendix's case analysis; numerical comparisons in the paper show much smaller ratios, so tightening the constant to single digits is a plausible next step that would not require a new scheme.
  • The cut-set lower bound assumes full-entropy intermediate values; re-running the gap analysis under a source-correlation model is a direct testable extension, since correlated Map outputs could make the true optimal shuffle load smaller than the bound.
  • The shuffle-aware rule's ability to beat the homogeneous optimum suggests heterogeneity can be actively exploited rather than merely compensated for, though only when the average load is high enough that zero-padding is not the dominant cost.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies the computation-communication tradeoff in a heterogeneous MapReduce system where nodes have different computation loads and can be assigned different numbers of output functions. It proposes a two-step file allocation (compulsory batches followed by decentralized-cache-style optional replication) and a coded shuffling scheme with zero-padding, and derives a closed-form achievable load for arbitrary computation load vector m and function assignment w (Theorem 1). It then proposes computation-aware and shuffle-aware function assignments and claims, in Corollary 1, that for average load below 0.55 the computation-aware load is within a constant factor 115 of the optimal load of an equivalent homogeneous system, and for average load at least 0.55 the shuffle-aware load is within the same constant factor. Numerical comparisons with prior heterogeneous schemes are also provided.

Significance. If the main claim holds, the paper gives a useful extension of coded MapReduce to general heterogeneous nodes: the achievable load is explicit, the two function-assignment rules are simple, and the homogeneous limit in Remark 1 correctly recovers the known result of Li et al., which is a good consistency check. The paper compares against an external benchmark (the homogeneous optimum) rather than fitting parameters, and the shuffle-aware construction is reported to outperform existing schemes in some numerical regimes. The main weakness is that the constant-gap argument for the low-average-load regime relies on a cut-set lower bound that is not valid under the stated system model; without an added standard entropy/independence assumption, that half of Corollary 1 is not established. The high-average-load half does not use this lower bound and appears sound. I also note that the construction requires exact integrality of sub-batch sizes and function counts, and the paper does not quantify rounding losses.

major comments (2)
  1. [Appendix B and Section II (Lemma 1, Eq. (23))] Lemma 1 is not valid under the model as stated. Section II defines the intermediate values v_{q,n} as elements of F_2^T but assigns no probability distribution to the input files or to the Map functions, so the entropy expressions H(...) in Eqs. (28)-(30) are undefined. The step (29a)-(29b) requires that IVs from disjoint file sets are independent and that each v_{q,n} carries full entropy T bits. These hypotheses do not follow from the model. Without them Lemma 1 is false: for K=2, N=Q=2, m=[1/2,1/2], w=[1/2,1/2], if every Map function g_{q,n} maps every file to the same T-bit string, then after computing one file a node knows all IVs and the true minimum communication load is 0, while (23) asserts L* >= 1/4. Since Corollary 2 and the mbar<0.55 part of Corollary 1 use this lemma (see Appendix A, Eqs. (24a)-(24b)), that half of the central claim is unproven. The fix is local and standard: add the assumption that input files are independent and uniform and that the induced IVs {v_{q,n}} are independent and uniformly distributed over F_2^T; with that hypothesis the steps (29a)-(29b) go through as written.
  2. [Sections III-B, III-C and IV-D (Theorem 1 and Corollary 1)] The achievability statement is conditional on exact integrality of all sub-batch sizes and function counts, but the main theorems and Corollary 1 do not state this as an explicit hypothesis. The construction in Theorem 1 uses sub-batches of size l_Ψ_k N and function counts w_k Q; if N or Q is not a multiple of the corresponding denominators, the described file partition and the zero-padded coded messages do not exist. Section IV-D gives divisibility requirements (for example, N must be a multiple of 1/(l_1 ∏ min{P_k,1-P_k}) in the r>0 case) but does not quantify the load increase when these conditions fail. Please restate Theorem 1 and Corollary 1 with an explicit asymptotic or divisibility condition, or provide a rounding-loss bound, so that the claimed constant gap applies to well-defined finite or limiting systems.
minor comments (5)
  1. [Section III-A] There is a typo in the subsection heading: 'subection' should be 'subsection'.
  2. [Appendix D, Lemma 2] In the statement of Lemma 2, the second displayed inequality is written with L1_A,2 on the left, but from the context and the proof it should be L2_A,2; please correct the label.
  3. [Section IV-D] The phrase 'N should scale with the multiple of ...' is ambiguous: it describes a divisibility condition, not an asymptotic scaling rate. Please clarify whether these are necessary, sufficient, or both.
  4. [Section IV-C] In Table I, the column header and the labels m1, m2 are easy to confuse with the computation-load vector m. Renaming the two test cases (for example, Case A and Case B) would improve readability.
  5. [Throughout] The paper would benefit from a sentence in Section II explicitly stating that all file sizes, IV lengths, and function outputs are measured in bits and that the communication load is normalized by QNT, since Lemma 1 depends on the total number of IVs rather than on the final output values.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the achievable-load derivation is self-contained and the comparison benchmark is external.

full rationale

The paper's derivation chain is not circular. The achievable communication load in Theorem 1 is obtained by an explicit two-step file allocation (eqs. (7)-(10)) and an explicit XOR/zero-padding shuffle strategy; the load expressions (12)-(15) are computed from the proposed scheme, not from the quantity being predicted. The function assignments wCom and wShu are closed-form choices that minimize or simplify the derived expression, which is standard design rather than circularity. The benchmark L*_Hom is taken from the external prior work of Li et al. [3], and the constant-gap proof bounds LA against the lower bound LLower from Lemma 1 and then bounds LLower/L*_Hom by elementary inequalities; L*_Hom is not reconstructed from LA. No parameter is fitted to data, and no derived claim is equivalent to its input by definition. The principal caveat is in Appendix B: the cut-set proof of Lemma 1 needs the intermediate values for disjoint files to be independent and to carry full T bits of entropy, an assumption not stated in the Section II model; if violated, the lower bound can fail (e.g., constant map outputs would make the true optimum zero). That is an unstated-assumption/correctness gap, not a circular reduction. There are no load-bearing self-citations; the cited results [3], [15], [16] are external and used as a benchmark or design inspiration, not to define the paper's own achievability claim.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard information-theoretic inequalities, the prior homogeneous optimal tradeoff, and idealizations about file counts and IV independence. No free parameters are fitted to data; the threshold 0.55 is a proof-splitting choice rather than a fitted constant.

assumptions (4)
  • domain assumption Intermediate values v_{q,n} are independent and uniformly distributed, so H(V_{W,M}) = |W||M|T bits for any W,M.
    Needed for the cut-set lower bound in Lemma 1 (Appendix B); not stated in Section II.
  • domain assumption The optimal load of the equivalent homogeneous system is the lower convex envelope of (mbar, (1-mbar)/(K mbar)) from prior work.
    Used as the external benchmark in Corollary 1; cited from the homogeneous coded computing result.
  • domain assumption N and Q are large enough that all sub-batch sizes l_k^Psi N and function counts w_k Q are integers.
    Stated at the end of Section II; the paper only bounds the required scaling and does not analyze rounding losses.
  • standard math The summation identities in equations (12)-(14) follow the decentralized caching analysis of prior work.
    The paper cites prior decentralized caching results for the derivation steps; accepted background.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Heterogeneous Coded Distributed Computing: Joint Design of File Allocation and Function Assignment." pith.science (2026). https://pith.science/paper/PELDTRCW

@misc{pith2026190806715,
  author       = {Pith},
  title        = {Pith review of: Heterogeneous Coded Distributed Computing: Joint Design of File Allocation and Function Assignment},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PELDTRCW}},
  note         = {Machine review of arXiv:1908.06715}
}
read the original abstract

This paper studies the computation-communication tradeoff in a heterogeneous MapReduce computing system where each distributed node is equipped with different computation capability. We first obtain an achievable communication load for any given computation load and any given function assignment at each node. The proposed file allocation strategy has two steps: first, the input files are partitioned into disjoint batches, each with possibly different size and computed by a distinct node; then, each node computes additional files from its non-computed files according to its redundant computation capability. In the Shuffle phase, coded multicasting opportunities are exploited thanks to the repetitive file allocation among different nodes. Based on this scheme, we further propose the computation-aware and the shuffle-aware function assignments. We prove that, by using proper function assignments, our achievable communication load for any given computation load is within a constant multiplicative gap to the optimum in an equivalent homogeneous system with the same average computation load. Numerical results show that our scheme with shuffle-aware function assignment achieves better computation-communication tradeoff than existing works in some cases.

Figures

Figures reproduced from arXiv: 1908.06715 by the authors.

Figure 1
Figure 1. The two-step file allocation strategy. 1) Map phase design: The proposed file allocation strategy in the Map phase has two steps. In the first step, the strategy is to allocate the input files among all the nodes exclusively as equal as possible, which may result in that the nodes with low computation load are exhausted while the nodes with high computation load still have extra computing capacity. Specifically, in … view at source ↗
Figure 2
Figure 2. Communication load L with K = 3 and K = 12. TABLE I: Communication load L with K = 12: 1) m1: mk = 1 6 for k ∈ [1 : 6], mk = 1 3 for k∈[7:12]; 2) m2: mk = 1 6 for k∈[1:6], mk = 1 2 for k∈[7:12]. Scheme L m m1 m2 [13] 0.528 0.497 [14] 0.357 0.185 Even FA 0.448 0.397 Computation-aware FA 0.371 0.255 Shuffle-aware FA 0.315 0.175 FA in [14] 0.349 0.208 In our file allocation strategy, if r > 0, we can prove that l1 ≤ · … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages

  1. [1]

    MapReduce: Simplified data proc essing on large clusters,

    J. Dean and S. Ghemawat, “MapReduce: Simplified data proc essing on large clusters,” Commun. ACM , vol. 51, no. 1, pp. 107–113, Jan. 2008

    work page 2008

  2. [2]

    Performance mode ling of mapreduce jobs in heterogeneous cloud environments ,

    Z. Zhang, L. Cherkasova, and B. T. Loo, “Performance mode ling of mapreduce jobs in heterogeneous cloud environments ,” in IEEE 6th Int. Conf. Cloud Comput. (CLOUD) , June 2013, pp. 839–846

    work page 2013

  3. [3]

    A fun damental tradeoff between computation and communication in distributed computing,

    S. Li, M. A. Maddah-Ali, Q. Y u, and A. S. Avestimehr, “A fun damental tradeoff between computation and communication in distributed computing,” IEEE Trans. Inf. Theory , vol. 64, no. 1, pp. 109–128, Jan 2018

    work page 2018

  4. [4]

    A new combinatorial desig n of coded distributed computing,

    N. Woolsey, R. Chen, and M. Ji, “A new combinatorial desig n of coded distributed computing,” in IEEE ISIT , June 2018

    work page 2018

  5. [5]

    Leveraging codi ng techniques for speeding up distributed computing,

    K. Konstantinidis and A. Ramamoorthy, “Leveraging codi ng techniques for speeding up distributed computing,” in IEEE GLOBECOM, Dec 2018

    work page 2018

  6. [6]

    Storage, computation, an d communication: A fundamental tradeoff in distributed computing,

    Q. Yan, S. Yang, and M. Wigger, “Storage, computation, an d communication: A fundamental tradeoff in distributed computing,” in IEEE ITW , Nov 2018

    work page 2018

  7. [7]

    Load scheduling f or distributed edge computing: A communication-computation tradeoff,

    M. Zhao, W. Wang, Y . Wang, and Z. Zhang, “Load scheduling f or distributed edge computing: A communication-computation tradeoff,” Peer-to-Peer Networking and Applications , Oct 2018. [Online]. Available: https://doi.org/10.1007/s12083-018-0695-4

    work page doi:10.1007/s12083-018-0695-4 2018

  8. [8]

    A sca lable framework for wireless distributed computing,

    S. Li, Q. Y u, M. A. Maddah-Ali, and A. S. Avestimehr, “A sca lable framework for wireless distributed computing,” IEEE/ACM Trans. Networking , vol. 25, no. 5, pp. 2643–2654, Oct 2017

    work page 2017

Show all 16 references
  1. [9]

    Wireless MapReduce distribu ted computing,

    F. Li, J. Chen, and Z. Wang, “Wireless MapReduce distribu ted computing,” in IEEE ISIT , June 2018

    2018

  2. [10]

    On heterogen eous coded distributed computing,

    M. Kiamari, C. Wang, and A. S. Avestimehr, “On heterogen eous coded distributed computing,” in IEEE GLOBECOM , Dec 2017, pp. 1–7

    2017

  3. [11]

    Coding for edge-facilitated wireless distribute d computing with heterogeneous users,

    ——, “Coding for edge-facilitated wireless distribute d computing with heterogeneous users,” in 51st Asilomar Conf. Signals, Syst. Comput. , Oct 2017, pp. 536–540

    2017

  4. [12]

    On distributed computing with heterogeneous communication constraints,

    N. Shakya, F. Li, and J. Chen, “On distributed computing with heterogeneous communication constraints,” in 52nd Asilomar Conf. Signals, Syst. Comput. , Oct 2018, pp. 1795–1799

    2018

  5. [13]

    Cascaded coded distribu ted computing on heterogeneous networks,

    N. Woolsey, R. Chen, and M. Ji, “Cascaded coded distribu ted computing on heterogeneous networks,” in IEEE ISIT , July 2019

    2019

  6. [14]

    Coded distributed computing with heterogeneous f unction assignments,

    ——, “Coded distributed computing with heterogeneous f unction assignments,” 2019. [Online]. Available: http://arxiv.org/abs/1902.10738

    2019 arXiv

  7. [15]

    Decentralized coded ca ching attains order-optimal memory-rate tradeoff,

    M. A. Maddah-Ali and U. Niesen, “Decentralized coded ca ching attains order-optimal memory-rate tradeoff,” IEEE/ACM Trans. Networking, vol. 23, no. 4, pp. 1029–1040, Aug 2015

    2015

  8. [16]

    Fundamental limits o f heterogenous cache,

    S. Wang, W. Li, X. Tian, and H. Liu, “Fundamental limits o f heterogenous cache,” 2015. [Online]. Available: http://arxiv.org/abs/1504.01123

    2015 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.