{"id":"e81e7a23-d202-4dc3-a4d1-7543d3abd180","arxiv_id":"1908.06715","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A two-step file allocation and two function-assignment rules give a constant-factor-optimal communication-computation tradeoff for heterogeneous MapReduce systems.","lead":"This paper designs a coded MapReduce scheme for clusters where nodes have different computation speeds, jointly choosing which files each node stores and which output functions it computes. The scheme is proved to stay within a constant factor of the optimal communication load for a homogeneous cluster with the same average speed.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1's lower bound needs an unstated full-entropy/independence assumption; without it the constant-gap claim for ¯m<0.55 is unproven (e.g., constant IVs give L*=0 but bound says L*≥1/4).","rationale":"The reader's weakest_assumption pinpoints the same issue, and I agree it is the most load-bearing one. The paper's headline contribution is Corollary 1's constant multiplicative gap. Its low-average-load branch (¯m<0.55) is proven only via Corollary 2, whose proof relies entirely on Lemma 1's cut-set lower bound. The upper-bound construction (Theorem 1) and the shuffle-aware branch (¯m≥0.55, which compares Theorem 3 directly to L*_Hom) do not depend on Lemma 1 and seem internally consistent. I checked the homogeneous specialization in Remark 1, the reordering argument in (12)-(14), and the AM-HM steps in Appendix A; they are consistent. The integrality requirement on N and Q is a real but secondary issue: the paper itself acknowledges it in Section IV-D and tabulates the required magnitudes, so it is a completeness limitation rather than a threat to the asymptotic claim. The missing entropy/independence hypothesis is more serious because it affects the validity of the converse. The concrete counterexample shows Lemma 1 cannot be rescued by a convention that communication load is worst-case over files, since the model as written includes constant Map functions. Once the standard full-entropy assumption is added, the proof of Lemma 1 is routine and the rest of the gap analysis stands. This is a one-line model amendment, not a fatal flaw in the scheme, so the appropriate disposition is the reader's CONDITIONAL, not rejection. No change to the reader's verdict is needed.","tokens_in":24104,"tokens_out":18214,"duration_ms":193813,"concrete_test":"Run the following allowed-instance check against the Section II model: take K=2, N=Q=2, m=[1/2,1/2], w=[1/2,1/2], and choose g_{q,n}(f_n)=0^T for all q∈[2], n∈[2]. Each node stores/computes one file, but because all IVs are the known constant 0^T, each node can evaluate its assigned Reduce function with zero communicated bits, so the minimum shuffle load is L*=0. Lemma 1's formula (23) gives max_T (1-∑_{k∈T}m_k)∑_{k∈T}w_k = 1/4 (attained by T={1} or {2}). Thus, unless Section II is amended to exclude degenerate Map functions or to assume full-entropy independent IVs, Lemma 1 is false. The same check also confirms the minimal fix: adding the independence/uniformity hypothesis makes (29b) valid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix B's cut-set lower bound (Lemma 1, eq. (23)) is the load-bearing step for the ¯m<0.55 half of Corollary 1: Corollary 2 bounds LA/L* by 16+70e using Lemma 1, and Corollary 1 multiplies this by LLower/L*_Hom<5/9. The proof step (29a)-(29b) needs H(V_{∪W_k, files not in ∪M_k} | V_{:, ∪M_k}) to be at least (∑_{k∈T} w_k) (1-∑_{k∈T} m_k) Q N T. This requires (i) IVs from disjoint file sets to be independent and (ii) every IV v_{q,n} to carry full T bits of entropy, independent across q and n. Section II only defines v_{q,n}∈F_2^T and never states a distribution on input files or a non-degeneracy condition on the Map functions. The assumption is not innocuous: if g_{q,n} maps every file to the same T-bit string, a node that has computed one file already knows all IVs, so L*=0. For K=2, N=Q=2, m=[1/2,1/2], w=[1/2,1/2], Lemma 1 would nevertheless assert L*≥(1-1/2)·(1/2)=1/4, a contradiction. Hence Lemma 1 is false as stated, and the claimed constant gap to L*_Hom for ¯m<0.55 is not established. The ¯m≥0.55 half of Corollary 1 is independent of Lemma 1 and appears sound. The fix is to add the standard assumption that input files are independent and uniform and the IVs {v_{q,n}} are independent and uniformly distributed over F_2^T; with that hypothesis (29a)-(29b) go through unchanged.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24487,"tokens_out":7510,"duration_ms":87451,"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":[{"comment":"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.","section":"Appendix B and Section II (Lemma 1, Eq. (23))"},{"comment":"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.","section":"Sections III-B, III-C and IV-D (Theorem 1 and Corollary 1)"}],"minor_comments":[{"comment":"There is a typo in the subsection heading: 'subection' should be 'subsection'.","section":"Section III-A"},{"comment":"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.","section":"Appendix D, Lemma 2"},{"comment":"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.","section":"Section IV-D"},{"comment":"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.","section":"Section IV-C"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper's contribution is incremental but potentially useful, and the numerical comparison with [10], [13], and [14] appears fair. The main technical problem is the unstated full-entropy/independence assumption in Lemma 1; because the counterexample is immediate and the fix is a standard model assumption, I do not regard this as a reject. I would ask the authors to add the assumption explicitly, verify that all statements referencing Lemma 1 (especially Corollary 2 and the mbar<0.55 case of Corollary 1) are updated, and make the integrality/rounding status of the achievability result precise. The claim should also be framed as a gap to the homogeneous optimum, not as a true heterogeneous optimality result, to match what is actually proved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nQuick take: this is a real contribution to the heterogeneous MapReduce literature, but the constant-factor guarantee for low average load is not actually proven as the paper now stands. The fix is straightforward, so I would still send it to a referee.\n\nWhat's new: a general achievable scheme for arbitrary K, computation loads m, and function assignments w. The two-step file allocation (compulsory plus optional files) and the two function-assignment rules (computation-aware and shuffle-aware) are genuine extensions over the K=3 and block-heterogeneous results. The closed-form load expression in Theorem 1 is useful, and the shuffle-aware assignment genuinely beats the homogeneous lower bound in some regimes. The numerical work is honest and modest.\n\nWhere the paper needs strengthening: Lemma 1 in Appendix B is the load-bearing lower bound for the mbar<0.55 half of Corollary 1. The proof jumps from (29a) to (29b) assuming that IVs from disjoint file sets are independent and that each v_{q,n} carries full T bits of entropy. The system model in Section II never states a distribution on the input files or a non-degeneracy condition on the Map functions. Without it, Lemma 1 is false: constant Map functions make L*=0 while the bound gives a positive value. I checked the specific counterexample in the stress-test note—constant IVs, K=2, N=Q=2—and it lands. So the claimed constant gap to L*_Hom for mbar<0.55 is not established. The mbar>=0.55 half does not use Lemma 1 and looks fine. Also minor: the scheme needs N and Q large enough for all sub-batch sizes to be integers; the paper acknowledges this and gives scaling conditions, but never quantifies rounding losses. That is minor.\n\nNone of this is fatal to the core scheme. Add the standard assumption (independent uniform files or IVs with full entropy), and the lower-bound proof goes through. Then the constant-gap result should hold. Citations look appropriate; the paper builds on the right prior work.\n\nBottom line: this is a serious paper with a fixable gap. I would give it a careful referee rather than desk reject. If you work on coded distributed computing, the achievable scheme and the shuffle-aware assignment are worth knowing.\n\nBest.","headline":"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.","tokens_in":24999,"tokens_out":3805,"would_cite":true,"duration_ms":37972,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68P20","94A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["coded distributed computing","MapReduce","heterogeneous computation load","file allocation","function assignment","communication-computation tradeoff","coded multicasting","constant multiplicative gap"],"falsifier":"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.","tokens_in":23892,"feed_emoji":"🔀","tokens_out":10488,"duration_ms":102395,"temperature":0.7,"pith_summary":"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.","feed_headline":"Unequal node speeds need not inflate MapReduce shuffle load","feed_subtitle":"File allocation plus load-aware function assignment keeps shuffle traffic within a factor of 115 of the homogeneous ideal.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the MapReduce decomposition $\\phi_q = h_q(g_{q,1}(f_1),\\dots,g_{q,N}(f_N))$ and the Map-Shuffle-Reduce model used throughout.","marker":"[1]"},{"why":"Supplies the homogeneous optimal load $L^*_{\\mathrm{Hom}}$ used as the benchmark and the original coded-distributed-computing file-allocation idea.","marker":"[3]"},{"why":"Provides the prior optimal heterogeneous scheme for $K=3$ with even function assignment that the paper compares against.","marker":"[10]"},{"why":"Gives a prior heterogeneous-function-assignment scheme whose larger load the numerical comparison shows the new scheme improving on.","marker":"[13]"},{"why":"Introduces the shuffle-aware-style function assignment for another heterogeneous model and gives the comparison baseline for the zero-padding argument.","marker":"[14]"},{"why":"Provides the decentralized-placement product formula and the summation identity referenced as Theorem 3, used to collapse the multicast-load sums in equations (12)-(13).","marker":"[16]"}],"fun_headline_variants":["Heterogeneous MapReduce: constant-factor tradeoff found","Mixed-speed clusters: shuffle load stays near ideal","File allocation + function assignment: gap to ideal is constant","Shuffle-aware design tames uneven node speeds","MapReduce on heterogeneous nodes: within 115 of ideal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Heterogeneous MapReduce: constant-factor tradeoff found","Mixed-speed clusters: shuffle load stays near ideal","File allocation + function assignment: gap to ideal is constant","Shuffle-aware design tames uneven node speeds","MapReduce on heterogeneous nodes: within 115 of ideal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000191,"raw_usage":{"total_tokens":1350,"prompt_tokens":958,"completion_tokens":392,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":315}},"tokens_in":574,"tokens_out":392,"duration_ms":5138,"temperature":1.0,"reasoning_tokens":315,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:38:01.294846+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"MapReduce: Simplified data proc essing on large clusters,","cited_arxiv_id":null,"evidence_quote":"Defines the MapReduce decomposition $\\phi_q = h_q(g_{q,1}(f_1),\\dots,g_{q,N}(f_N))$ and the Map-Shuffle-Reduce model used throughout."},{"cited_title":"A fun damental tradeoff between computation and communication in distributed computing,","cited_arxiv_id":null,"evidence_quote":"Supplies the homogeneous optimal load $L^*_{\\mathrm{Hom}}$ used as the benchmark and the original coded-distributed-computing file-allocation idea."},{"cited_title":"On heterogen eous coded distributed computing,","cited_arxiv_id":null,"evidence_quote":"Provides the prior optimal heterogeneous scheme for $K=3$ with even function assignment that the paper compares against."},{"cited_title":"Cascaded coded distribu ted computing on heterogeneous networks,","cited_arxiv_id":null,"evidence_quote":"Gives a prior heterogeneous-function-assignment scheme whose larger load the numerical comparison shows the new scheme improving on."},{"cited_title":"Coded Distributed Computing with Heterogeneous Function Assignments","cited_arxiv_id":"1902.10738","evidence_quote":"Introduces the shuffle-aware-style function assignment for another heterogeneous model and gives the comparison baseline for the zero-padding argument."}],"review_version":1}