{"id":"44444983-38c4-4b56-b3b8-1ff0cf8595dc","arxiv_id":"1908.09271","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Spreading a file across multiple independently coded storage systems adds only a small transmission overhead when the systems use diverse codes, and a bounded, quantified overhead when they share one code.","lead":"This paper studies file downloads that pull data from multiple storage systems at once, without the systems coordinating with each other. It shows that using different error-correcting codes in different systems makes the download nearly as efficient as a perfectly coordinated one.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section III's Theorem 1 is sound; the load-bearing concern is the empirical Section IV claim that AR4JA LDPC decodes like a binary random code after k+3 symbols under an unproven 8-bit block-alignment assumption.","rationale":"The reader's assessment matches mine: Section III is solid, while Section IV is empirically under-supported and contains an unjustified modeling assumption about LDPC block alignment. My stress-test focused on the single most load-bearing issue, the LDPC treatment, because the paper's 'maximum code diversity' claim depends on it. I did not identify an internal inconsistency in the main theorem; the Markov model and concentration proof hold up. The concern is not that the simulation is outside consensus, but that it is not verifiable from the manuscript: no code, no trial counts, no error bars, and no justification that grouping bits into blocks preserves the relevant rank statistics for a structured binary code. The proposed concrete test directly checks whether the 99.9% result at k+3 symbols survives without block alignment, which would settle whether the Section IV conclusion is an artifact. Since the reader already recommends conditional acceptance pending such support, my read does not change the verdict: the paper should remain conditional, with the condition being release of simulation artifacts and justification or correction of the LDPC block-alignment assumption.","tokens_in":9461,"tokens_out":14455,"duration_ms":156660,"concrete_test":"Reimplement the Section IV simulation at the LDPC-only vertex using the AR4JA [1280,1024]2 code: estimate Pr(rank of received generator submatrix = 1024) for 1048 received bit positions sampled (i) in aligned 8-bit blocks as in the paper, (ii) uniformly among all 1280 bit positions, and (iii) in 8-bit blocks after a random cyclic shift of the bit ordering, with at least 10^4 trials per condition. If the 99.9% success rate is not reproduced in (ii) and (iii), the block-alignment assumption is the undefended load-bearing step. Also report the original code, data, and trial counts for Fig. 6.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theoretical contribution in Section III is internally consistent: the Markov chain in Eq. (5) matches the stated round-robin sampling-without-replacement protocol, Lemma 1 and Corollary 1 are correct, and the variance bound in Eqs. (17)-(23) establishes the concentration needed for Theorem 1. I find no mathematical error there. The load-bearing weakness is in Section IV, the basis for the paper's central practical message that code diversity enables close-to-optimal uncoordinated delivery. The claim that any mixture of lifted RS, RLN, and AR4JA LDPC codes decodes with 99.9% probability after k+3 F256 symbols, 'independent of the mixture,' rests entirely on an unreported simulation. The crucial modeling step is the assertion that 'block-aligned erasures' of eight F2 columns faithfully mimic F256 symbol erasures and that 'the LDPC-C's performance is unaffected' by this grouping. For RS and RLN, erasing whole F256 symbols is the native erasure model; for the binary LDPC code there is no such symbol structure, and the claim is asserted without proof, data, or trial counts. A structured binary code's rank distribution over random subsets of 1048 generator-matrix columns is not implied by the MDS property of RS/RLN and need not match a binary random linear code. If the 99.9% figure is an artifact of the chosen 8-bit alignment, the Section IV conclusion and the Section V recommendation collapse.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes uncoordinated content delivery from S storage systems that use the same MDS code, modeling the number of unseen codeword symbols as a time-inhomogeneous Markov chain and deriving the asymptotic fraction u_S(τ) = (1 − τ/S)^S of unseen symbols after τn received transmissions (Theorem 1, Eq. (11)). From this it obtains a storage–transmission tradeoff via the relation R = 1 − (1 − τ̃/S)^S in Eq. (26). The paper then presents an empirical case study (Section IV) in which a mixture of an RLN code, an RS code, and an AR4JA LDPC code is downloaded without coordination, claiming that decoding succeeds with 99.9% probability after k + 3 F256 symbols regardless of the mixture, and concluding that binary LDPC codes can be treated as binary RLN codes for this purpose.","tokens_in":9635,"tokens_out":3848,"duration_ms":40251,"significance":"The Section III result is a clean, self-contained characterization of a natural coupon-collector tradeoff and appears to be correct; if the empirical Section IV claim were fully substantiated, the paper would provide a practically relevant design principle for content-centric storage systems. However, the central 'code diversity' message currently rests on an unreported simulation with an unproven modeling assumption, so the paper's overall significance is contingent on that evidence being supplied.","major_comments":[{"comment":"The claim that after downloading one, two, and three additional F256 symbols the probability of successful decoding reaches 90%, 99%, and 99.9%, 'independent of the mixture,' is not reproducible from the manuscript: there is no description of the number of simulation trials, the random seeds, the exact generator-matrix constructions (e.g., the specific RS evaluation points, the RLN coefficient distribution, and the AR4JA parity-check matrix), or the procedure for mixing symbol types. Without these details, a reader cannot verify the load-bearing empirical result; the authors should provide the code and data or a complete experimental protocol with confidence intervals.","section":"Section IV, Fig. 6 and the paragraph 'Fig. 6 shows ...'"},{"comment":"The statement 'while the LDPC-C's performance is unaffected' by block-aligned erasures is asserted without proof or supporting data. For a binary LDPC code there is no inherent F256 symbol structure, and grouping eight F2 coordinates into a block can materially change the rank distribution of the reduced generator matrix; the MDS properties of RS and RLN codes do not imply anything about the AR4JA code's behavior under this grouping. The paper needs either a formal argument that the AR4JA rank profile over block-aligned subsets matches that of a binary random linear code, or a systematic empirical study of the grouping's effect on the decoding probability.","section":"Section IV, paragraph beginning 'We thus get ...'"},{"comment":"The conclusion that 'binary LDPC-Cs can be treated as binary RLN-Cs' is an extrapolation far beyond the single AR4JA code and the single parameter set (n = 1280, k = 1024) studied. Even if the simulation were fully reproducible, the paper provides no reason to expect this equivalence to hold for other LDPC codes, other rates, or other block sizes; if this is intended as a general design rule, it requires supporting analysis, and otherwise the claim should be explicitly restricted to the studied code and parameters.","section":"Section IV, concluding paragraph 'As a result of our empirical case study ...'"}],"minor_comments":[{"comment":"The phrase 'F orn→∞' contains a typo and should read 'For n→∞'.","section":"Theorem 1 statement"},{"comment":"The expression for τ̃ writes the S-th root as 'S√ 1−R', which is ambiguous; it should be typeset as (1−R)^{1/S} or \\(\\sqrt[S]{1-R}\\).","section":"Eq. (26)"},{"comment":"The system model introduces storage erasures (the \\(\\hat{c}_i\\) vectors), but the Markov-chain analysis in Section III assumes all n codeword symbols are available for transmission. The paper should state explicitly that the tradeoff characterization ignores storage erasures, or incorporate them into the model.","section":"Section II system model vs. Section III analysis"},{"comment":"The caption says 'minimum number of k = 128 symbols' but the text refers to k′ = 1024 base-field F2 symbols; please clarify consistently that the 128 symbols are F256 symbols, which correspond to 128 blocks of 8 F2 symbols.","section":"Fig. 6 caption and surrounding text"},{"comment":"The limit argument uses the informal approximations labeled (a), (b), and (c) without rigorous error bounds; providing explicit bounds on the approximation errors would make the proof of convergence of the expectation fully rigorous, although the concentration part is standard.","section":"Theorem 1 proof"}],"recommendation":"major_revision","confidential_remarks":"The theoretical Section III is sound and could stand alone as a publishable contribution. The empirical Section IV, however, is the basis for the paper's headline 'code diversity' claim and is currently unsupported by any reproducible evidence or analysis. I would urge the editor to require the authors to provide simulation code/data and either justify the block-aligned grouping assumption for LDPC codes or significantly weaken the claims before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is worth your attention for Section III alone. Theorem 1—for S uncoordinated storage systems sending distinct symbols round-robin without replacement, the fraction of unseen symbols after τn transmissions converges to (1−τ/S)^S—is a clean, new characterization. The derivation is elementary but exact: the recursion for the expectation is correct, the variance bound via Chebyshev is standard, and the finite-n plots match the formulas. The resulting storage-versus-transmission tradeoff curves are useful design guidance.\n\nThe second half is where I get off the train. Section IV claims that mixing RS, RLN, and AR4JA LDPC codes lets a user decode with 99.9% probability after k+3 F256 symbols, independent of the mixture. That claim rests entirely on an unreported simulation: no code, no data, no trial counts, no error bars. More importantly, the LDPC part depends on the assertion that block-aligned erasures of eight F2 columns faithfully mimic F256 symbol erasures, and that the LDPC-C's performance is unaffected. For RS and RLN, symbol alignment is native; for a binary LDPC code there is no F256 symbol structure. The rank distribution of a structured generator matrix over random subsets of 1048 columns need not match a binary random linear code. The stress-test note is on target: if that 99.9% figure is an artifact of the chosen 8-bit alignment, the Section IV conclusion and the Section V recommendation collapse.\n\nThere is also a smaller modeling gap: the theoretical part in Section III assumes each storage system holds all n codeword symbols and sends each at most once. Storage erasures are mentioned in Section II but never enter the analysis. That is a simplification, not a fatal flaw, but readers should know the tradeoff curves apply only to the erasure-free case.\n\nAll told, this is a solid theoretical contribution with an under-documented empirical add-on. The math in Section III holds up; Section IV needs to ship its artifacts and justify the LDPC block-alignment step before the main practical message is credible. The paper deserves a serious referee—I'd accept it for review, not desk reject—but I'd make the authors release the simulation code and redo the LDPC analysis.\n\nFor a reading group, I'd bring it as an example of a clean asymptotic argument paired with a cautionary empirical appendix.","headline":"Solid new characterization of the multi-server coupon collector tradeoff; the empirical code-diversity claim rests on an under-documented simulation with an unproven LDPC block-alignment assumption.","tokens_in":10255,"tokens_out":2765,"would_cite":true,"duration_ms":26245,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Mixing codes cuts uncoordinated download waste to 3 extra symbols","keywords":["uncoordinated content delivery","coded storage","coupon collector problem","code diversity","Reed-Solomon codes","random linear network coding","LDPC codes","transmission overhead"],"falsifier":"Run the Section III protocol with $S=2$ servers holding the same MDS code of large block length $n$ and rate $R=1/2$, and measure the fraction of unseen symbols after $\\tau n$ transmissions for several $\\tau$; if the values deviate from $(1-\\tau/2)^2$ beyond the variance bound, the theorem is wrong. For the diversity claim, repeat many trials of downloading exactly 131 $\\mathbb{F}_{256}$ symbols in a one-third mix of RS, RLN, and LDPC symbols from $[160,128]_{256}$-equivalent codes and check whether decoding succeeds in at least $99.9\\%$ of trials regardless of mix order.","tokens_in":9149,"feed_emoji":"🗄️","tokens_out":9238,"duration_ms":84876,"temperature":0.7,"pith_summary":"This paper studies what happens when a user downloads a file from several independently operated storage systems that do not coordinate which coded symbols they transmit. For the case where all $S$ systems store the same maximum-distance-separable code of rate $R$, it proves that the fraction of codeword symbols still unseen after $\\tau n$ received transmissions converges to $(1-\\tau/S)^S$ as $n\\to\\infty$, giving a transmission overhead factor $\\delta = S(1-(1-R)^{1/S})/R$; storage redundancy can partially pay for the coupon-collector waste. For the opposite case, it reports that a mix of Reed-Solomon, random linear network, and LDPC codes decodes with probability $99.9\\%$ after $k+3$ transmitted symbols, independently of the mixture. The paper's message is that code diversity, which is the natural state of heterogeneous networks, turns uncoordinated delivery from a serious inefficiency into a near-optimal operation.","feed_headline":"Mixing codes cuts uncoordinated download waste to 3 extra symbols","feed_subtitle":"One MDS code on every server gives a coupon-collector curve; diverse codes decode after k+3 symbols.","key_machinery":"The load-bearing object of Section III is a time-varying Markov chain tracking $U_\\ell$, the number of codeword symbols the user has not yet seen after $\\ell$ transmissions. At round $\\ell$ the active storage system samples uniformly from the $n - \\lfloor \\ell/S \\rfloor$ symbols it has not previously transmitted, so when $i$ symbols are unknown the probability that the next symbol is new is $r_{i,\\ell} = i/(n - \\lfloor\\ell/S\\rfloor)$; the chain either moves to $i-1$ or stays at $i$. The argument uses the exact mean recursion and a variance bound of order $O(n)$ to prove convergence in probability to the deterministic curve $u_S(\\tau) = (1-\\tau/S)^S$. For the diversity result, the machinery is a field-lifting construction: parity-check equations over $\\mathbb{F}_{256}$ are expanded over $\\mathbb{F}_2$ by replacing multiplication by $\\alpha$ with the matrix $m(\\alpha)$, and erasures are applied in aligned blocks of eight binary columns so that the $\\mathbb{F}_{256}$-symbol structure is preserved. This lifting is what lets the three different code families be decoded jointly by Gaussian elimination on the stacked generator matrix.","core_discovery":"The paper's central claim is a closed-form description of the coupon collector's problem that arises when $S$ storage systems all use the same $[n,k]_q$ MDS code and alternately transmit a uniformly random codeword symbol they have not previously sent. The number of unseen symbols $U_\\ell$ after $\\ell$ transmissions obeys the recursion $\\mathbb{E}[U_{\\ell+1}] = (1 - 1/(n - \\lfloor\\ell/S\\rfloor)) \\, \\mathbb{E}[U_\\ell]$, and in the large-block limit the fraction of unseen symbols is $u_S(\\tau) = (1-\\tau/S)^S$. Inverting this for rate $R$ gives the transmission factor $\\delta = S(1-(1-R)^{1/S})/R$, the multiplicative penalty for uncoordinated same-code delivery. The paper's second claim is empirical: if the storage systems instead use different codes, specifically a Reed-Solomon code, a random linear network code over $\\mathbb{F}_{256}$, and a binary AR4JA LDPC code, then after downloading only $k+3$ $\\mathbb{F}_{256}$-symbols the user can decode with probability $99.9\\%$, essentially independently of how the three code families are mixed. The interpretation is that maximum code diversity makes the collection of received symbols behave like a small-field random linear network code, which is close to the optimal rate of information per transmitted symbol.","pith_inferences":["The formula $u_S(\\tau)=(1-\\tau/S)^S$ has a reading the paper does not spell out: for a fixed symbol, it is the probability that none of the $S$ servers has picked it by normalized time $\\tau$, i.e., the fraction unseen is the survivor function of a coupon collector seen from the symbol's point of view. That symmetry suggests a direct connection to order statistics of independent geometric draws.","The $k+3$ result is demonstrated for $[160,128]_{256}$ and $[1280,1024]_2$ parameters and for the specific LDPC code AR4JA; a natural extension, not pursued in the paper, is to test whether the 'three extra symbols' constant persists for other rates, field sizes, and LDPC ensembles.","If storage systems transmit at different rates or hold different numbers of symbols, the symmetric round-robin assumption breaks; an obvious extension is a weighted or heterogeneous version of the Markov chain, which would tell operators whether the same-code penalty worsens when one server is much faster than the others.","The block-aligned erasure assumption is natural for RS and RLN symbols but is an approximation for LDPC: a testable extension is to randomize the alignment or use LDPC codes over $\\mathbb{F}_{256}$ directly, and check whether the near-optimal decoding threshold survives."],"forward_implications":["For any fixed storage factor $\\sigma = 1/R > 1$, the transmission factor remains finite as $S\\to\\infty$, so a user can pull from arbitrarily many same-code servers with bounded uncoordinated overhead.","The curve $\\delta = S(1-(1-R)^{1/S})/R$ gives operators a quantitative tradeoff: extra storage buys a directly computable reduction in transmission overhead, and vice versa.","With diverse codes, no duplicate-suppression or scheduling feedback is needed; downloading $k+3$ symbols suffices for $99.9\\%$ success, so a digital-fountain style 'send until I stop you' protocol is nearly optimal.","The field-lifting construction plus Gaussian elimination means the mixed-code scheme can be decoded with standard erasure-decoding software, without belief propagation.","Operators can emulate near-optimal performance even without designing new codes by randomly recoding stored symbols before transmission, effectively converting any code into a random linear code at the transport layer."],"supporting_citations":[{"why":"introduces the digital-fountain model of a server streaming coded symbols until the user stops it, which motivates the uncoordinated protocol","marker":"[25]"},{"why":"supplies the multi-code distributed-storage construction used to lift and combine codes from different families over one base field","marker":"[26]"},{"why":"provides the random linear network coding construction used as one of the three diversified codes","marker":"[27]"},{"why":"defines Reed-Solomon codes over finite fields, used as the second code in the diversity case study","marker":"[28]"},{"why":"gives the protograph-based AR4JA LDPC code construction used as the binary code in the mix","marker":"[30]"},{"why":"specifies the AR4JA code parameters [1280,1024]_2 and the rationale for the LDPC choice","marker":"[31]"},{"why":"supports the decision to decode by Gaussian elimination rather than belief propagation for the mixed non-sparse system","marker":"[33]"}],"fun_headline_variants":["Diverse codes fix uncoordinated storage download waste","Random code mix trims uncoordinated download overhead","Coupon collector's waste solved by code diversity","Mixing codes cuts storage overhead: k+3 symbols enough","Uncoordinated delivery: diverse codes beat single code"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The tradeoff curve in Theorem 1 assumes that every storage system, in a fixed round-robin order, sends a uniformly random symbol among those it has not yet transmitted, with no user feedback and no coordination between systems; if real systems schedule symbols, allow repeats, or miss stored symbols, the curve does not describe the download.","fun_headline_variants_meta":{"raw":{"variants":["Diverse codes fix uncoordinated storage download waste","Random code mix trims uncoordinated download overhead","Coupon collector's waste solved by code diversity","Mixing codes cuts storage overhead: k+3 symbols enough","Uncoordinated delivery: diverse codes beat single code"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000191,"raw_usage":{"total_tokens":1390,"prompt_tokens":1038,"completion_tokens":352,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":654,"completion_tokens_details":{"reasoning_tokens":275}},"tokens_in":654,"tokens_out":352,"duration_ms":3262,"temperature":1.0,"reasoning_tokens":275,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:18:16.058100+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the Section III protocol with $S=2$ servers holding the same MDS code of large block length $n$ and rate $R=1/2$, and measure the fraction of unseen symbols after $\\tau n$ transmissions for several $\\tau$; if the values deviate from $(1-\\tau/2)^2$ beyond the variance bound, the theorem is wrong. For the diversity claim, repeat many trials of downloading exactly 131 $\\mathbb{F}_{256}$ symbols in a one-third mix of RS, RLN, and LDPC symbols from $[160,128]_{256}$-equivalent codes and check whether decoding succeeds in at least $99.9\\%$ of trials regardless of mix order.","supporting_citations":[{"cited_title":"A digital fountain approach to reliable distribution of bulk data,","cited_arxiv_id":null,"evidence_quote":"introduces the digital-fountain model of a server streaming coded symbols until the user stops it, which motivates the uncoordinated protocol"},{"cited_title":"Multi-code distributed storage,","cited_arxiv_id":null,"evidence_quote":"supplies the multi-code distributed-storage construction used to lift and combine codes from different families over one base field"},{"cited_title":"A random linear network coding approach to multicast,","cited_arxiv_id":null,"evidence_quote":"provides the random linear network coding construction used as one of the three diversified codes"},{"cited_title":"Polynomial codes over certain finite fields,","cited_arxiv_id":null,"evidence_quote":"defines Reed-Solomon codes over finite fields, used as the second code in the diversity case study"},{"cited_title":"Protograph based LDPC codes with minimum distance linearly growing with block size,","cited_arxiv_id":null,"evidence_quote":"gives the protograph-based AR4JA LDPC code construction used as the binary code in the mix"},{"cited_title":"TM synchronization and channel coding – summary of concept and rationale,","cited_arxiv_id":null,"evidence_quote":"specifies the AR4JA code parameters [1280,1024]_2 and the rationale for the LDPC choice"}],"review_version":1}