{"id":"f0852d8d-20c3-4df2-9715-3cb83999d235","arxiv_id":"1908.05666","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Resolvable designs from single parity-check codes shrink the file and job counts of coded distributed computing while preserving its communication-load benefit.","lead":"Resolvable designs, a combinatorial structure built from simple error-correcting codes, reduce the number of files or jobs needed by coded MapReduce schemes that cut network traffic during the shuffle phase. On Amazon EC2, the authors report up to 4.69x faster TeraSort and 4.31x faster matrix-vector products than uncoded baselines.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"I read the multi-job protocol as the main contribution. The proof has no missing step other than Lemma 3, and that lemma is standard and verifiable for the SPC-code design. The reader's weakest-assumption identification points to the right place, but the concern does not land because the property follows directly from the information-set structure of the code. The load derivations are exact, the comparison with CCDC is algebraically consistent, and public code supports the experimental portion. I preserve the CONDITIONAL verdict only because of the abstract/body speedup inconsistency and the absence of an empirical multi-job CCDC baseline, which are presentation/comparison issues rather than flaws in the central theorem.","tokens_in":24663,"tokens_out":33107,"duration_ms":352164,"concrete_test":"Verify Lemma 3 for small parameters, e.g., (q,k)=(3,4) and (4,3), by enumerating all SPC codewords (u_1,...,u_{k−1},∑u_i) over Z_q, forming the blocks B_{i,l}, and checking every choice of k−1 blocks from distinct parallel classes for intersection size exactly 1. If any counterexample appears, re-examine the single-job and multi-job correctness proofs. A secondary check is to recompute the CCDC load formula at μ=(k−1)/K and confirm that it algebraically equals Eq. (7).","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The central claim—CAMR matches CCDC's load with an exponentially smaller job count—survives a careful check. The only unproved combinatorial input is Lemma 3 (intersection of k−1 blocks from k−1 distinct parallel classes has size 1), which the paper cites to [26]. This property is true for the SPC-code construction: the code is the set of q^{k−1} length-k codewords over Z_q in which any k−1 coordinates form an information set; fixing k−1 coordinate values determines the unique remaining coordinate, so the corresponding blocks intersect in exactly one point. This makes the single-job proof in Section IV-D and the multi-job stages in Section V-C internally consistent. The load algebra also checks out: Stage 1 contributes 1/[q(k−1)], Stage 2 contributes (q−1)/[q(k−1)], Stage 3 contributes (q−1)/q, and the sum equals [k(q−1)+1]/[q(k−1)], which is exactly Eq. (8) evaluated at μ=(k−1)/K. The abstract/body speedup discrepancy (2.6x vs 2.4x/3.01x) and the absence of a multi-job CCDC experiment are presentation and comparison issues rather than threats to the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two coded distributed computing schemes based on resolvable designs generated from single parity-check (SPC) codes. For a single job with K = k q servers, the data set is split into N = q^{k-1} files assigned to servers according to the block incidence of the design; the scheme achieves communication load L = 1/(k-1) * (1 - k/K) with computation load r = k, giving a factor r-1 reduction relative to an uncoded scheme with the same redundancy, while using far fewer files than the CDC scheme. For multiple jobs with aggregatable functions, the CAMR scheme uses J = q^{k-1} jobs and storage fraction μ = (k-1)/K, and its three-stage shuffle protocol attains load L = [k(q-1)+1]/[q(k-1)], which is shown to equal the CCDC load in Eq. (8) with an exponentially smaller number of jobs. The paper presents EC2 TeraSort experiments (up to 4.69x over the uncoded baseline) and matrix-vector multiplication experiments (up to 4.31x), with code made publicly available.","tokens_in":24858,"tokens_out":15231,"duration_ms":147201,"significance":"If the results hold, the main contribution is practical: CAMR matches CCDC's communication load with an exponentially smaller number of jobs, and the single-job scheme obtains a substantial fraction of CDC's gain with tractable subpacketization (e.g., N = 128 for K = 16, r = 8 versus 12870 files for the prior scheme). The load derivations are carried out by exact counting, are parameter-free, and are verified against the external CCDC expression; no curve fitting is involved. The experimental section is unusually thorough for this line of work, including code release, memory-allocation accounting, and a discussion of MPI communicator overhead. The main caveats are presentation issues and the reliance on a cited combinatorial lemma rather than an in-paper proof, neither of which undermines the central claims.","major_comments":[],"minor_comments":[{"comment":"The abstract's claim of a '2.6x over prior work' speedup does not match Section IV-E, which reports a maximum gain over the prior coded TeraSort of 3.01x when memory allocation is included and 2.4x when it is excluded. Please reconcile these numbers or remove the unsubstantiated 2.6x figure.","section":"Abstract; §IV-E"},{"comment":"Lemma 3, the intersection property of k-1 blocks from distinct parallel classes, is stated as 'proved in [26]' and is the load-bearing combinatorial fact for both the single-job correctness proof and the multi-job Stage 2/Stage 3 protocols. Since the proof is short and the lemma is central, the journal version should include it in the appendix or restate the exact theorem from [26] with a proof, rather than only citing the prior paper.","section":"§IV-D; §V-C"},{"comment":"The discussion around inequality (a) is confusing: the displayed lower bound binom(kq,k) ≥ q^k is monotone increasing in q, so the statement that '(a) is maximum when q = 2' is not accurate as written. The conclusion q^k > q^{k-1} is correct regardless, but the sentence should be rephrased.","section":"§V-F"},{"comment":"The claim that the proposed scheme reduces the communication load by a factor of r-1 should state explicitly that the comparison is against an uncoded scheme with the same computation load r. The experimental discussion compares against the uncoded r = 1 baseline and reports a Shuffle-time gain of 13.125 for r = 8, which is a different ratio and may confuse readers.","section":"§IV-D; §IV-E"},{"comment":"The proof of Lemma 2 refers to a 'complete graph' on G\\{U_j} and C, while Algorithm 1 specifies a complete bipartite graph; the terminology should be fixed.","section":"Appendix; Algorithm 1"},{"comment":"Figure 1, the MPI_Comm_Split execution time plot, lacks axis labels, units, and a precise description of the benchmark configuration; please add these details.","section":"Fig. 1"},{"comment":"In the sentence 'that speedup would be 169.1/90.857.74 = 14.41', the multiplication sign between 90.85 and 7.74 is missing; please fix the typo.","section":"§V-H"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a journal extension of the authors' GLOBECOM 2018 and ISIT 2019 papers ([20] and [21]); the multi-job load equality with CCDC already appears in [21], so the editor may wish to confirm that the journal version's additional contribution (the unified resolvable-design framework, the single-job subpacketization analysis, and the EC2 experiments) satisfies the journal's novelty bar. I do not see a correctness issue that would justify rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nTwo things you should know about this paper. First, the central claim holds up: the multi-job CAMR scheme gives exactly the same communication load as CCDC (eq. 8), while needing q^{k-1} jobs instead of binom(K, mu K+1), and the single-job scheme uses q^{k-1} files instead of binom(K,r) at a small load cost. Second, the genuinely new content is not the constructions — those appeared in the same authors' GLOBECOM 2018 and ISIT 2019 papers — but the EC2 implementation, the MPI communicator-limit analysis, and the public code.\n\nWhat the paper does well: the load derivations are exact counting, no curve-fitting anywhere. Lemma 2 is proved in the appendix. The multi-job load algebra checks out: stages 1, 2, 3 sum to [k(q-1)+1]/[q(k-1)], matching CCDC evaluated at mu=(k-1)/K. The experiments are carefully done for what they cover: a 100 Mbps cap, memory allocation time reported separately because the prior repo ignores it, and a head-to-head comparison against the Coded TeraSort repository. The MPI_Comm_Split cost plot is a real practical point, not filler — the prior scheme's binom(K, r+1) groups collapse under communicator limits. The citation pattern is acceptable: [20], [21], and [26] are published results, and the final load expressions are independently derived against CCDC.\n\nSoft spots, in proportion. The abstract's '2.6x over prior work' conflicts with the body's 3.01x (with memory allocation) and 2.4x (without). That is sloppy and needs fixing. 'Exhaustive experimental results' is an overstatement for two workloads, and the multi-job case has no empirical CCDC comparison, only theory. Lemma 3, which carries the single-job correctness proof and the multi-job stage-2/stage-3 protocols, is stated without proof, cited to the same group's [26]. The stress-test note is right that the property is true for the SPC-code construction — fixing k-1 coordinates of a length-k systematic codeword determines the last one, so the blocks intersect in exactly one point. So this is a presentation gap, not a broken load-bearing wall, but a referee should ask for an inline proof. Last, the EC2 numbers cannot be independently reproduced from the preprint alone; the public code and phase-level timings reduce that worry but do not remove it.\n\nWho gets value: people working on coded distributed computing and on practical MapReduce/MPI overheads. This is a solid, honest attempt to make coded schemes viable at realistic file and job counts. A serious referee should engage with it. My recommendation: send it out for review, with a request to reconcile the abstract/body numbers, prove Lemma 3 inline, and soften 'exhaustive'.","headline":"The central claim survives a careful check — same load as CCDC with exponentially fewer jobs — and the real new value is the EC2 validation; minor consistency fixes and an inline proof for Lemma 3 are needed before acceptance.","tokens_in":25457,"tokens_out":3291,"would_cite":true,"duration_ms":32316,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B05","94B05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Coded MapReduce gets practical with far fewer files and jobs","keywords":["coded distributed computing","communication load","resolvable designs","single parity-check codes","MapReduce","coded multicasting","aggregate functions","shuffle phase"],"falsifier":"Enumerate all choices of $k-1$ blocks from distinct parallel classes for the SPC-code design with small composite parameters such as $q=4, k=3$; if any intersection has size different from 1, the Lemma 3-based correctness argument fails. For prime $q$, a brute-force check over small $k$ and $q$ would confirm the property computationally and isolate where a proof is needed.","tokens_in":24411,"feed_emoji":"🧩","tokens_out":6937,"duration_ms":62304,"temperature":0.7,"pith_summary":"This paper tries to establish that resolvable designs—combinatorial arrangements of points into parallel blocks, generated from single parity-check codes—can make coded MapReduce practical by drastically reducing the number of files a job must be split into and the number of jobs a batch must contain. For a single job, the proposed scheme needs $N = q^{k-1}$ files and cuts the shuffle load by a factor of $r-1$ relative to uncoded transmission, whereas the prior coded scheme required a combinatorial number of files to reach its lower load. For multiple jobs whose functions can be aggregated, the CAMR scheme achieves exactly the communication load of the compressed coded distributed computing scheme, $L = [k(q-1)+1]/[q(k-1)]$, while requiring only $q^{k-1}$ jobs instead of $\\binom{K}{\\mu K+1}$. The paper supports this with theory and with cluster experiments reporting speedups of $4.69\\times$ for TeraSort and $4.31\\times$ for distributed matrix-vector multiplication over uncoded baselines.","feed_headline":"Coded MapReduce gets practical with far fewer files and jobs","feed_subtitle":"Parity-check-code designs keep prior communication loads while shrinking required file and job counts.","key_machinery":"The central object is the resolvable design $(X,\\mathcal{A})$ obtained from the codewords of a $(k,k-1)$ single parity-check code over $\\mathbb{Z}_q$: the point set $X = [q^{k-1}]$ indexes files or jobs, and each block $B_{i,l}$ collects the points whose $i$-th codeword coordinate equals $l$. The blocks split into $k$ parallel classes of $q$ blocks each, and the crucial combinatorial property (Lemma 3) is that any $k-1$ blocks chosen from distinct parallel classes intersect in exactly one point. This property guarantees that in every $k$-server communication group, each server is missing a unique chunk that all other servers hold, so the paper's Algorithm 1—splitting each chunk into $k-1$ packets and having each server broadcast an XOR of the packets it can provide—delivers all missing chunks in $k$ transmissions of total size $Bk/(k-1)$. The same machinery is reused in stage 1 and stage 2 of the multi-job CAMR protocol.","core_discovery":"On its own terms, the paper claims that a resolvable design built from a $(k,k-1)$ single parity-check code over $\\mathbb{Z}_q$ simultaneously dictates file placement and defines the multicast groups for the shuffle phase. In the single-job case each server group of size $k$ has the property that every server misses exactly one data chunk that the other $k-1$ servers share; using XOR-based coded multicast, $k$ transmissions of size $B/(k-1)$ let each server recover its missing chunk, giving communication load $L = \\frac{1}{k-1}\\left(1-\\frac{k}{K}\\right)$ with only $N = q^{k-1}$ files. In the multi-job case, associating jobs with design points and servers with blocks yields a three-stage protocol whose total load is $L_{\\mathrm{CAMR}} = \\frac{k(q-1)+1}{q(k-1)}$, identical to the load of prior compressed coded distributed computing for the same storage fraction $\\mu = (k-1)/K$, but with exponentially fewer jobs. The paper further claims that this translates into measured speedups of $4.69\\times$ over uncoded TeraSort and $4.31\\times$ over uncoded matrix-vector multiplication.","pith_inferences":["Beyond the paper: because the design construction works for any modulus $q$ (not necessarily prime), the same protocol could be instantiated at parameter values matched to specific cluster sizes or communicator limits, with the load and subpacketization tradeoff controlled by $q$.","Beyond the paper: the Lemma 3 intersection property is the foundation of both correctness proofs and is imported without proof; an independent proof or exhaustive enumeration for small composite $q$ would make the scheme self-contained and reveal whether the property extends beyond the parity-check construction.","Beyond the paper: the practical speedups depend on multicast being close to a linear broadcast; on clusters where tree or hardware multicast is much cheaper, the observed gains could be larger than the load analysis predicts, while on networks with high per-group setup costs the advantage of fewer groups would grow further."],"forward_implications":["A single MapReduce job can be processed with $N = q^{k-1}$ files instead of the combinatorial $\\binom{K}{r}\\eta$ files required by prior coded schemes, removing a major practical obstacle to coded shuffling.","For a batch of aggregatable jobs, the same communication load as compressed coded distributed computing is achievable with $q^{k-1}$ jobs rather than $\\binom{K}{\\mu K+1}$, so the method works when only modest numbers of jobs are submitted.","The communication load of the multi-job scheme is $L = \\frac{k}{k-1} - \\frac{1}{q}$, so increasing $q$ at fixed $k$ smoothly trades more jobs for lower shuffle traffic.","In the measured TeraSort runs, the single-job scheme achieved up to $4.69\\times$ total speedup over uncoded sorting, and the multi-job matrix-vector experiments reached $4.31\\times$ over the uncoded baseline."],"supporting_citations":[{"why":"defines the single-job coded MapReduce model and the file-count baseline $N=\\binom{K}{r}\\eta$ that the proposed scheme avoids.","marker":"[9]"},{"why":"introduces the compressed coded distributed computing scheme whose communication load and job-count requirement CAMR matches and improves.","marker":"[1]"},{"why":"supplies the resolvable-design construction and the Lemma 3 intersection property on which the correctness proofs rest.","marker":"[26]"},{"why":"provides the prior coded TeraSort implementation used as the experimental baseline in the single-job comparison.","marker":"[14]"},{"why":"is the posted prior TeraSort code that the experiments build on and compare against.","marker":"[27]"},{"why":"records the authors' earlier single-job scheme that this paper extends to the multi-job setting.","marker":"[20]"}],"fun_headline_variants":["Resolvable designs slash file and job counts in coded MapReduce","Practical coded distributed computing via resolvable designs","Speed up MapReduce with resolvable design codes","Faster distributed computing with fewer redundant files","Resolvable designs bring coded computing to real clusters"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 3, stated without proof and cited from earlier work, that any $k-1$ blocks chosen from $k-1$ distinct parallel classes of the SPC-code resolvable design intersect in exactly one point; if that intersection ever has a different size, the single-job and multi-job shuffle protocols lose their guarantee that each server misses a unique shared batch.","fun_headline_variants_meta":{"raw":{"variants":["Resolvable designs slash file and job counts in coded MapReduce","Practical coded distributed computing via resolvable designs","Speed up MapReduce with resolvable design codes","Faster distributed computing with fewer redundant files","Resolvable designs bring coded computing to real clusters"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000276,"raw_usage":{"total_tokens":1708,"prompt_tokens":1066,"completion_tokens":642,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":682,"completion_tokens_details":{"reasoning_tokens":568}},"tokens_in":682,"tokens_out":642,"duration_ms":6834,"temperature":1.0,"reasoning_tokens":568,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:17:13.951074+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all choices of $k-1$ blocks from distinct parallel classes for the SPC-code design with small composite parameters such as $q=4, k=3$; if any intersection has size different from 1, the Lemma 3-based correctness argument fails. For prime $q$, a brute-force check over small $k$ and $q$ would confirm the property computationally and isolate where a proof is needed.","supporting_citations":[{"cited_title":"A fundamental tradeoff between computation and communication in distributed com- puting,","cited_arxiv_id":null,"evidence_quote":"defines the single-job coded MapReduce model and the file-count baseline $N=\\binom{K}{r}\\eta$ that the proposed scheme avoids."},{"cited_title":"Compressed coded dis- tributed computing,","cited_arxiv_id":null,"evidence_quote":"introduces the compressed coded distributed computing scheme whose communication load and job-count requirement CAMR matches and improves."},{"cited_title":"Coded caching schemes with reduced subpacketization from linear block codes,","cited_arxiv_id":null,"evidence_quote":"supplies the resolvable-design construction and the Lemma 3 intersection property on which the correctness proofs rest."},{"cited_title":"Coded terasort,","cited_arxiv_id":null,"evidence_quote":"provides the prior coded TeraSort implementation used as the experimental baseline in the single-job comparison."},{"cited_title":"Repository of TeraSort for prior implementation","cited_arxiv_id":null,"evidence_quote":"is the posted prior TeraSort code that the experiments build on and compare against."},{"cited_title":"Leveraging coding techniques for speeding up distributed computing,","cited_arxiv_id":null,"evidence_quote":"records the authors' earlier single-job scheme that this paper extends to the multi-job setting."}],"review_version":1}