{"id":"318a6fb5-0499-4526-8acc-02a6e1b8cc28","arxiv_id":"2412.19649","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A randomized algorithm achieves O(n log n/(γk)) per-peer queries for Byzantine-resilient Download with any fault fraction β<1, plus dynamic-adversary and crash-fault protocols and a single-round lower bound.","lead":"This paper gives protocols that let a network of peers download an entire n-bit file from a trusted external source while tolerating any fraction of Byzantine failures, with near-optimal per-peer query counts. It also proves that any single-round solution forces every peer to read essentially the whole file, so the multi-round structure is unavoidable.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.5 is not the weak point; the load-bearing gap is Section 6's asynchronous time analysis, which assumes bounded message delays absent from the stated model.","rationale":"The reader's verdict of CONDITIONAL is appropriate, but not for the reason stated in the reader's weakest_assumption. That assumption concerns the adversary seeing fresh coins of round t before choosing the faulty set; the model in Section 1.1 explicitly denies the adversary this power, and Lemma 2.2's Chernoff argument only needs the faulty set for a round to be fixed before that round's coins are generated. The actual load-bearing problem is the asynchronous time analysis in Section 6. The model promises unbounded finite message delays, while Lemma 6.11 and Theorem 6.12 analyze time as though each message is delivered within one time unit. This is an internal inconsistency, not merely a disagreement with an external convention. It affects a stated contribution of the abstract: query-optimal deterministic Download in asynchronous crash-fault settings with O(n) time. The query-complexity and correctness parts of those theorems do not depend on the unit-delay assumption, so the appropriate remedy is a conditional acceptance requiring the time analysis to be either restated as phase complexity or moved to a bounded-delay asynchronous model. The reader's rationale already flags this section, so the overall CONDITIONAL verdict does not need to change.","tokens_in":34239,"tokens_out":23973,"duration_ms":494410,"concrete_test":"Formalize the asynchronous model as unbounded finite delays and re-derive the phase-completion recurrence of Lemma 6.11 without any 'after 1 time unit' step. Concretely, introduce an explicit delay bound D only if it is added to the model; if no such D is present, show that the time until a nonfaulty peer receives k-f stage-2 responses cannot be bounded as a function of n alone. If the best provable bound is O(D·n) or 'O(n) phases' rather than O(n) time, then Theorem 6.12 must be weakened or the model amended to bounded-delay asynchrony.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The strongest claim, Theorem 2.5, appears internally sound under the stated adversary model; in particular, the reader's worry that the adversary might see round-t coins is excluded by Section 1.1, which grants the adversary knowledge only of random bits generated up to round t-1. The real internal inconsistency is in the crash-fault asynchrony results. Section 1.1 defines asynchrony as 'an adversary may delay every message by any finite amount of time,' i.e., unbounded delay. Yet Lemma 6.11's time proof states 'after n/k·(f/k)^p time, every phase p stage 1 response... is heard by M (even slow ones)' and the refinement claims 'after 1 time unit, every message is delivered (even by slow peers).' These assertions require a uniform upper bound on message delivery delay, say D=1, which is not part of the model. With truly unbounded finite delays, no wall-clock O(n) bound follows; the proof's recurrence bounds phase count, not elapsed time. Thus Theorem 6.12's O(n) time claim is unsupported as stated. Correctness and query complexity of Algorithm 9 do not use the unit-delay assumption and appear fine.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Download problem in the Data Retrieval model, in which k peers in a clique must learn an n-bit array stored at a trusted external source, with up to βk Byzantine or crash faults and with query cost as the primary measure. The main claimed contributions are: (i) a synchronous randomized Byzantine-resilient protocol with query complexity O(n log n/(γk)) for every β<1 (Theorem 2.5), closing a gap left by [3]; (ii) a one-round lower bound showing that every peer must query essentially the whole input (Theorem 3.6); (iii) faster O(log n)-round protocols against a dynamic adversary in point-to-point and broadcast models (Theorems 4.5 and 4.12); and (iv) deterministic crash-fault protocols for synchronous and asynchronous networks, including an O(n) time asynchronous algorithm (Theorems 5.16, 6.4, 6.12). The techniques are blacklisting with gradually increasing query probabilities, sifting with decision trees, a boosting loop in the broadcast model, and view-based primary-backup algorithms for crash faults.","tokens_in":34464,"tokens_out":17454,"duration_ms":168089,"significance":"If the stated results hold, the paper makes a substantial contribution: it removes the β<1/3 restriction or the additive √n term that were present in the prior randomized Byzantine results, and it gives the first query-optimal Byzantine Download protocol for arbitrary β<1. The proofs are largely self-contained and the protocol sections include pseudocode; the Chernoff/blacklisting argument in Section 2 and the decision-tree/sifting argument in Section 4 are coherent and appear sound under the stated adversary model. I specifically checked the reviewer's concern that the adversary might see round-t coins before choosing the faulty set in round t: Section 1.1 explicitly grants the adversary only the random bits generated up to round t-1, so Theorem 2.5 is not undermined by that worry. However, two load-bearing pieces are not yet in defensible form: the asynchronous time analysis in Section 6.2 assumes bounded message delays that are absent from the stated model, and the lower bound in Section 3 conflates the number of peers with the input length. These issues require correction before the paper's claims are fully supported.","major_comments":[{"comment":"The O(n) time claim is not supported by the stated asynchronous model. Section 1.1 defines full asynchrony as \"an adversary may delay every message by any finite amount of time,\" i.e., there is no uniform upper bound on delivery delay. Lemma 6.11's proof asserts that \"after n/k·(f/k)^p time, every phase p stage 1 response by a nonfaulty peer is heard by M (even slow ones),\" and the refinement in §6.2 asserts that \"after 1 time unit, every message is delivered (even by slow peers).\" Both assertions presuppose a bound on message-delivery delay that is not part of the model. With genuinely unbounded finite delays, the recurrence bounds the number of phases, not wall-clock time, so Theorem 6.12's O(n) time bound is unsupported as written. The same unbounded-delay issue affects the stated T=Õ(n/k) in Theorem 6.4, whose proof contains no time argument. Please either add and state an explicit bounded-delay assumption (e.g., every message is delivered within one time unit) or weaken the time claims to phase/round counts. The correctness and query-complexity parts of Algorithm 9 do not appear to rely on the unit-delay assumption.","section":"§6.2, Lemma 6.11 and Theorem 6.12"},{"comment":"This section conflates the number of peers with the input length. The model has k peers and an n-bit array, but §3 writes \"Let V be a set of n peers\" and simultaneously denotes the input vector by X={b1,...,bn}. Lemma 3.3's extremal calculation q(i)=∏_v(1−p_v(i))≤(1−1/n)^n uses the same symbol n for both quantities. If k and n are distinct, as they are in the DR model (where n≫k is the typical case), the correct bound is (1−1/N)^k with N the input length; this can be close to 1 when k≪N, and the claimed p(Rℓ)≥1−e^{-1} does not follow. Thus Theorem 3.6 as written is proved only for the special case k=n. Please restate the lower bound with distinct symbols for the number of peers and the number of bits, or explicitly restrict the theorem to k=n and state that restriction, and then adapt the argument.","section":"§3, Lemma 3.3 and Theorem 3.6"},{"comment":"The derivation of Corollary 4.7 is mis-stated. The text says it is obtained by applying Observation 4.6 to \"the point-to-point algorithm of Section 2,\" but Algorithm 1 of Section 2 runs for O(n log k) rounds, not O(log n) rounds, and the broadcast simulation of that algorithm would require messages of size at least O(n log n/(γk)) because of the query bits in the first epoch. If the intended source is Algorithm 4 of Section 4.2, then the message-size bound O(n/(γk)) still omits the log factor coming from ϕ=(n/(γk))·8(c+1)ln n. Please correct the reference and the stated bound, or use \tilde O notation consistently.","section":"§4.3, Corollary 4.7"}],"minor_comments":[{"comment":"The section assumes \"arbitrarily large messages can be sent in a single round,\" but this assumption is not stated in the model in Section 1.1, where per-round message size is O(log n) unless otherwise stated; please state this explicitly in the lower-bound section.","section":"§3, opening paragraph"},{"comment":"The claimed message size O(1) is not immediate from the pseudocode, where each vote is written as ⟨M,i,b_i^M=b⟩ and would need O(log n+log k) bits; please clarify that the epoch index and peer identity are implicit from the round structure and the synchronous network, or revise the message-size statement.","section":"§2, Theorem 2.5"},{"comment":"The table lists \"Message Size O(log n)\" for Theorem 6.4, but the theorem statement says M=O(nk), which is a total-message-complexity bound; please separate message size from total message complexity and state the packetization assumption.","section":"Table 2, Theorem 6.4 row"},{"comment":"The \"slight modification of the code\" that avoids blocking on unnecessary stage-2 responses is described only in prose; since Theorem 6.12's improved time bound depends on this modification, please include the modified pseudocode or a precise specification of the blocking rule.","section":"§6.2, paragraph after Lemma 6.11"},{"comment":"The word \"Retervial\" in \"Data Retervial model\" is a typo for \"Retrieval.\"","section":"§7, first paragraph"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for a theory-oriented distributed computing journal, and the main Byzantine-fault results appear sound under the stated adversary model. The two issues that block acceptance are the asynchronous time analysis in Section 6.2, which uses a bounded-delay assumption absent from the model, and the parameter conflation in the Section 3 lower bound. Both are fixable, but they affect central claims. The authors should also double-check the statement and derivation of Corollary 4.7 before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main take: this is the real resolution of the query-optimality question for Byzantine Download in the DR model. Theorem 2.5 closes the gap left by their DISC 2024 paper, achieving Q=O(n log n/γk) for any β<1, with T=O(n log k) and O(1)-size messages. The proof is self-contained, and the Chernoff-plus-blacklisting argument works. The single-round lower bound is also convincing: the message-swapping indistinguishability argument is clean and generalizes to broadcast. The dynamic-adversary and broadcast-model results are genuine extensions, even if they rely on larger messages.\n\nThe soft spot is the asynchronous time analysis in Section 6.2. The model says the adversary may delay every message by any finite amount of time, which is unbounded. Yet the proof of Lemma 6.11 asserts that after a fixed number of time units every message is delivered, and the refinement claims \"after 1 time unit, every message is delivered (even by slow peers).\" That is exactly a uniform bound on message delay, which is not stated in the model. With truly unbounded finite delays, you cannot assert any wall-clock bound; the recurrence bounds phase count, not elapsed time. So Theorem 6.12's T=O(n) is unsupported as stated. This does not affect the Byzantine sections or the correctness/query complexity of Algorithm 9, but it needs to be fixed, either by adding the standard unit-delay assumption explicitly or by downgrading the result to a phase-count bound. A minor issue: Section 3 uses n for both the number of peers and the number of bits; the lower bound is stated only for n peers, which is fine but should be cleaned up.\n\nWho gets value: anyone working on distributed retrieval, blockchain oracles, or BFT complexity. The paper is self-contained, does not lean on [3]'s theorems as inputs, and the main result is a genuine step forward. It deserves a serious referee, not a desk reject. I would send it to review with the understanding that the authors need to fix the async timing claim before acceptance.","headline":"Solid, significant paper that closes the β<1 query-optimality gap for Byzantine Download; the main results hold up, but the asynchronous crash-fault time analysis has a missing assumption.","tokens_in":35048,"tokens_out":5915,"would_cite":true,"duration_ms":54545,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68W15","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"A randomized protocol downloads an n-bit array at near-optimal per-peer query cost even when almost all peers are Byzantine.","keywords":["distributed download","data retrieval model","Byzantine faults","query complexity","blacklisting","crash faults","broadcast model","randomized algorithms"],"falsifier":"Strengthen the adversary to choose round $t$'s Byzantine set after seeing round $t$'s fresh coins, then run Algorithm 1 with $n=2^{20}$, $k=2^{10}$, $\\beta=0.9$, and check whether in any round $j$ the expected number of honest peers that flip heads falls below $2^{j-2}$; if it does, the gossip-learning invariant of Lemma 2.2 no longer holds and the stated query bound cannot be recovered by the same proof.","tokens_in":34050,"feed_emoji":"📥","tokens_out":12021,"duration_ms":95558,"temperature":0.7,"pith_summary":"This paper studies the Download problem in the Data Retrieval model: $k$ peers in a clique network must all learn an $n$-bit array stored in a trusted external source, by either querying the source directly (expensive) or exchanging messages, while up to $\\beta k$ peers may be Byzantine for any $\\beta \\in [0,1)$. The central contribution is a randomized protocol for the synchronous point-to-point model that achieves per-peer query complexity $O(n\\log n/(\\gamma k))$ with high probability, where $\\gamma=1-\\beta$, while tolerating any fraction $\\beta<1$ of Byzantine peers; this closes the gap left by prior work that either required $\\beta<1/3$ or incurred an additive $\\sqrt{n}$ in queries. The paper also gives faster $O(\\log n)$-round protocols for a dynamic adversary that can rotate the faulty set each round, near-optimal worst-case bounds in a broadcast model, a lower bound showing that single-round solutions force every peer to query essentially the entire array, and deterministic query-optimal protocols for crash faults in synchronous and asynchronous networks. A sympathetic reader would care because the result says that even when the adversary controls almost all peers, the cost of reading a large shared dataset can be kept within a logarithmic factor of the no-failure optimum.","feed_headline":"Near-optimal queries per peer even with a Byzantine majority","feed_subtitle":"With any fraction of faulty peers below 1, per-peer queries stay within a log factor of the no-fault optimum.","key_machinery":"The load-bearing mechanism is the per-epoch gossip-or-query decision with exponentially ramped query probability: in round $j$ of epoch $i$, a peer that has not yet learned bit $i$ tosses $2^j$ coins of bias $1/(\\gamma k)$, queries the source if any coin lands heads, and otherwise adopts a bit only if the number of votes for it reaches $2^{j-2}$. The proof's central invariants are the Blacklisting statement ($BL_i$) and Correctness statement ($C_i$), which together ensure, with high probability, that every peer that queries a bit queries the true value, that every blacklisted peer is genuinely Byzantine, and that the number of blacklisted peers in a query epoch is at least $(R_i - 2^f)/8$; this last inequality converts the total number of coin flips into a bound on total queries. The faster protocols in Section 4 replace blacklisting with sifting: peers randomly pick intervals of the array, broadcast the strings they read, and use $t$-frequent strings plus decision trees to determine the correct interval with few additional queries.","core_discovery":"The main discovery is Theorem 2.5: in the synchronous point-to-point model with Byzantine failures, there is a randomized algorithm for Download such that with high probability $Q=O(n\\log n/(\\gamma k))$, $T=O(n\\log k)$, and $M=O(nk^2)$, with messages of size $O(1)$. The algorithm works bit by bit in $n$ epochs; in each round of an epoch a peer either learns the bit by gossip learning when a decisive majority of non-blacklisted peers have voted for the same value, or by a direct query triggered by coin flips whose probability doubles each round. A peer blacklists any peer that sends a contradictory vote, and the charging argument at the heart of the proof shows that every wasteful query epoch forces enough Byzantine peers to be blacklisted to pay for the extra queries. Combined with a Chernoff bound on the number of heads among the biased coins, this yields the $O(n\\log n/(\\gamma k))$ query bound and closes the gap between the two previous randomized bounds, one restricted to $\\beta<1/3$ and one carrying an additive $\\sqrt{n}$.","pith_inferences":["The charging argument that pays for extra queries with newly blacklisted Byzantine peers suggests a general design principle: protocols for Byzantine data retrieval can be analyzed by budgeting redundant queries against the adversary's limited pool of faulty identities; this may extend to functions computed with partial downloads or to models with probabilistic fault guarantees.","The gap between the $O(\\log n)$-round protocol and the single-round lower bound leaves an open tradeoff curve: as the allowed number of rounds decreases from $\\log n$ to $1$, per-peer query cost should rise from $O(n\\log n/(\\gamma k))$ toward $\\Omega(n)$, and finding the exact curve is a natural next step.","The main algorithm's correctness depends on the adversary not seeing the current round's fresh random coins before choosing that round's faulty set; where random bits may leak earlier, one could derandomize the coin schedule or use committed randomness, at the cost of re-opening the query bound.","For blockchain-oracle style applications, the result implies that re-reading a large static dataset can be made cheap even with a faulty majority; the paper leaves temporal data open, but the per-epoch structure suggests incremental re-downloads could be amortized over time."],"forward_implications":["Download can be solved with query complexity $O(n\\log n/(\\gamma k))$ for every $\\beta<1$ in the synchronous point-to-point model, removing the previous $\\beta<1/3$ restriction and the additive $\\sqrt{n}$ term.","Because every computable function of the array can be computed after Download, all retrieval problems in the DR model inherit this query bound as a baseline in the synchronous Byzantine setting.","Against a dynamic Byzantine adversary that can change the faulty set every round, Download completes in $O(\\log n)$ rounds with expected query complexity $O(n\\log n/(\\gamma k))$ using messages of size $O(n)$, and in the broadcast model with worst-case $O((1/\\gamma)\\log^2 n)$ queries and messages of size $O(\\log n/\\gamma)$.","In the crash-fault model, deterministic protocols achieve optimal query complexity $O(n/(\\gamma k))$ in both synchronous and asynchronous settings, so the Byzantine deterministic lower bound is specific to Byzantine behavior rather than to unreliability in general.","Any single-round randomized protocol with at most $n-1$ queries per peer fails with constant probability when $\\beta\\approx 1/2$, so the trivial every-peer-queries-everything algorithm is essentially the only one-round solution."],"supporting_citations":[{"why":"Defines the Data Retrieval model and supplies the two prior bounds that this paper closes the gap between: beta<1/3 with optimal queries, or any beta<1 with an additive sqrt(n) in queries.","marker":"[3]"},{"why":"Introduces the primary-backup view-change approach used by the deterministic crash-fault protocols in Sections 5 and 6.","marker":"[2]"},{"why":"Supplies the consensus lower bound of f+1 rounds that motivates the view-change design of the Rapid Download protocol in Section 5.2.","marker":"[10]"}],"fun_headline_variants":["Byzantine majority? Download still near-optimal queries","Per-peer queries near-optimal even with Byzantine majority","Near-optimal query complexity for download under Byzantine faults","Randomized algorithm achieves near-optimal queries under any faulty majority","Download from external source: Byzantine-resilient near-optimal queries"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the Byzantine adversary, when choosing which peers are faulty at the start of round $t$, has not yet seen the fresh random coins that honest peers flip in round $t$; if it could see those coins first, the Chernoff argument that guarantees enough honest peers query or vote in each round could fail.","fun_headline_variants_meta":{"raw":{"variants":["Byzantine majority? Download still near-optimal queries","Per-peer queries near-optimal even with Byzantine majority","Near-optimal query complexity for download under Byzantine faults","Randomized algorithm achieves near-optimal queries under any faulty majority","Download from external source: Byzantine-resilient near-optimal queries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001179,"raw_usage":{"total_tokens":4930,"prompt_tokens":1064,"completion_tokens":3866,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":680,"completion_tokens_details":{"reasoning_tokens":3784}},"tokens_in":680,"tokens_out":3866,"duration_ms":26029,"temperature":1.0,"reasoning_tokens":3784,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T00:01:43.935469+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Strengthen the adversary to choose round $t$'s Byzantine set after seeing round $t$'s fresh coins, then run Algorithm 1 with $n=2^{20}$, $k=2^{10}$, $\\beta=0.9$, and check whether in any round $j$ the expected number of honest peers that flip heads falls below $2^{j-2}$; if it does, the gossip-learning invariant of Lemma 2.2 no longer holds and the stated query bound cannot be recovered by the same proof.","supporting_citations":[{"cited_title":"Byzantine Resilient Distributed Computin g on External Data","cited_arxiv_id":null,"evidence_quote":"Defines the Data Retrieval model and supplies the two prior bounds that this paper closes the gap between: beta<1/3 with optimal queries, or any beta<1 with an additive sqrt(n) in queries."},{"cited_title":"Alsberg and John D","cited_arxiv_id":null,"evidence_quote":"Introduces the primary-backup view-change approach used by the deterministic crash-fault protocols in Sections 5 and 6."},{"cited_title":"Fischer, Nancy A","cited_arxiv_id":null,"evidence_quote":"Supplies the consensus lower bound of f+1 rounds that motivates the view-change design of the Rapid Download protocol in Section 5.2."}],"review_version":1}