{"id":"7254bbc1-97ba-482c-9422-11317abeb8ee","arxiv_id":"2509.03755","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"First asynchronous solutions for the Download problem: optimal deterministic crash-tolerant protocols, near-optimal randomized Byzantine-tolerant protocols, and a new Ω(n/2) lower bound for β ≥ 1/2.","lead":"This paper presents the first asynchronous protocols for the distributed Download problem, where a group of peers must collectively retrieve a large external bit array while some peers may fail. It gives optimal per-peer query complexity for crash faults and near-optimal randomized results for Byzantine faults below half, plus a new lower bound for Byzantine majorities.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 11 undercounts leftover unknown bits at termination by a factor of k, so Theorem 12's O(n/γk) query bound is not established as written.","rationale":"The reader's weakest_assumption identifies exactly the same inconsistency: Lemma 11's termination-phase cost uses (n/k)·(f/k)^P instead of n·(f/k)^P, undercounting leftover unknown bits by a factor of k. This is load-bearing because it is the step that converts the geometric sum into the optimal O(n/(γk)) query bound. The protocol is plausible and the error appears repairable by extending the phase count to log_{k/f}(n), so I would not reject the paper; however, the theorem as stated is not proven. The Byzantine lower bounds and randomized protocols are not implicated by this concern. The appropriate disposition is CONDITIONAL, pending a corrected query-complexity analysis for the crash-fault protocol.","tokens_in":22339,"tokens_out":4074,"duration_ms":42700,"concrete_test":"Recompute Theorem 12's query complexity using Claim 10's correct bound. Fix k=10^4, f=5·10^3, n=10^6, so γ=0.5 and n/(γk)=200. Let P=log_{k/f}(n/k)=log_2(100)≈6.64. Claim 10 gives leftover unknown bits = n·(f/k)^P = 10^4·(0.5)^6.64 ≈ 10^4, while Lemma 11 predicts 1. Summing the per-phase costs n/k·(f/k)^p for p=0,...,P−1 gives ≈ 2·(n/k)=200, plus the leftover 10^4, so Q ≈ 10^200, contradicting the stated O(n/(γk)) bound. Then test the proposed repair: run to P'=log_{k/f}(n)=log_2(10^6)≈19.93 phases; verify that the sum of per-phase costs is still O(n/(γk)) and that the final leftover is 1, and check whether the time bound in Lemma 11 remains O(n/ϕ + log_{k/f}(ϕ)) under the larger phase count.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central crash-fault result (Theorem 12) relies on Lemma 11, which claims that at termination after P = log_{k/f}(n/k) phases, a peer queries at most (n/k)·(f/k)^P = 1 additional bit. But Claim 10 bounds the number of unknown bits per peer at the start of phase p by n·(f/k)^p, not (n/k)·(f/k)^p. At phase P, the number of unknown bits per peer is therefore n·(f/k)^P = k, not 1. The quantity (n/k)·(f/k)^p is the per-phase query cost, not the residual unknown count. This is not a cosmetic slip: the final direct query must cover all remaining unknown bits, so the correct additive term is k. Hence the query complexity is O(n/(γk) + k), which is not O(n/(γk)) when n = o(k^2). For example, with k=10^4, f=k/2, and n=k^{3/2}=10^6, the claimed bound is about 200, while the leftover term alone is 10^4. The proof can likely be repaired by running to P = log_{k/f}(n) phases, which leaves only 1 unknown bit and still gives sum_{p=0}^{P-1} (n/k)(f/k)^p = O(n/(γk)); however, the time analysis in Lemma 11 would need to be redone, and as written Theorem 12's query-optimality claim is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Distributed Data Retrieval (DR) model in asynchronous networks, focusing on the Download problem: every nonfaulty peer must learn an n-bit array X stored at an external source, while minimizing per-peer queries. The main positive result is a deterministic crash-fault protocol claimed to achieve optimal query complexity Q = O(n/(γk)) for any fraction β < 1 of crashes, with sublinear time and message complexity O(nk^2). For Byzantine faults, the paper proves that when β ≥ 1/2, every randomized asynchronous protocol has an execution in which some peer queries more than n/2 bits, and every deterministic protocol requires Q = n; for β < 1/2, it gives deterministic and randomized protocols with near-optimal query complexity. It also sketches an application to blockchain oracles. The Byzantine lower bounds and randomized protocols are mostly rigorous, but the crash protocol's query-optimality proof contains a concrete off-by-k error in the termination phase.","tokens_in":22738,"tokens_out":9322,"duration_ms":105708,"significance":"If the crash-fault result is repaired, this is a significant contribution: it is the first treatment of the DR model in asynchronous networks, and it shows a separation between crash and Byzantine faults in terms of achievable query complexity. The randomized Byzantine lower bound for β ≥ 1/2 is also notable because it extends the synchronous deterministic lower bound to randomized asynchronous protocols, ruling out randomization as a workaround in the majority-Byzantine regime. The protocols are concrete and the oracle application is a nice practical motivation. However, the central claimed result—deterministic query-optimal Download in the crash model—is not established as written because of a load-bearing error in the query-complexity analysis of Lemma 11, which affects Theorem 12. The paper does not ship machine-checked proofs or code, but the proof structure is otherwise mostly clear and reproducible.","major_comments":[{"comment":"The final additive term in the query bound is wrong. Claim 10 bounds the number of unknown bits per peer at the start of phase p by n·(f/k)^p. The quantity (n/k)·(f/k)^p is therefore the per-phase query cost after uniform reassignment, not the residual unknown-bit count. After P = log_{k/f}(n/k) phases, each nonfaulty peer still has n·(f/k)^P = k unknown bits, so the direct query performed on Line 41 costs k bits, not 1. Hence Lemma 11 supplies Q = O(n/(γk) + k), which is not O(n/(γk)) when n = o(k^2). Since Theorem 12's headline query-optimality claim rests on this bound, it is not established as written. The gap appears repairable, e.g. by running to P = log_{k/f}(n) phases so that the residual is 1 bit, but the time analysis in Lemma 11 would need to be redone; the current text needs revision before the result can be accepted.","section":"Section 2.2, Lemma 11 and Theorem 12"}],"minor_comments":[{"comment":"The table and contribution list state Q = Θ(n/(γk)), while Theorem 12 only proves an upper bound. If the matching lower bound is not proved or cited, the Θ notation should be replaced by O.","section":"Lemma 11 / Theorem 12 statement"},{"comment":"In the theorem statement, Q = O(n log n/(γ−βk)) appears to be a typo for Q = O(n log n/((γ−β)k)); the same typo appears in the contributions list.","section":"Theorem 20"},{"comment":"The text refers to 'Protocol 3' and 'Protocol 4' when the corresponding code blocks are labeled 'Algorithm 3' and 'Algorithm 4'. This is confusing and should be aligned.","section":"Section 3.4 / Algorithm numbering"},{"comment":"The proof of Theorem 13 defines EX^F_s as a 'synchronous execution' in a paper about asynchronous networks. Since asynchronous executions include synchronous ones, this is formally fine, but it should be stated explicitly to avoid confusion.","section":"Appendix A"},{"comment":"The final paragraph correctly notes the restrictive static-data assumption. This limitation is important and should also be stated in the model section, not only in the application section.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid contribution with interesting results, but the crash-fault query-optimality proof has a real gap that must be fixed before acceptance. The issue is localized and likely repairable, so I recommend major revision rather than rejection. There is no concern about scope or citation practice."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this is the first paper to take the Data Retrieval model into the asynchronous setting, and the crash-fault protocol plus the randomized Byzantine lower bound for β ≥ 1/2 are genuinely new. But the query-optimality proof for the main crash protocol has a real gap: Lemma 11 undercounts the leftover unknown bits at termination by a factor of k, so Theorem 12 as written is not established.\n\nThe paper does a few things well. The deterministic crash protocol is a natural extension of Algorithm 1 to f crashes, and the geometric decay idea—each phase reduces unknown bits by f/k—is clean. The randomized Byzantine lower bound in Section 3.1 is slick: the adversary delays half the peers and couples an all-zero execution with a one-1 execution; I checked the probability argument and it holds. The Byzantine upper bounds for β < 1/2 are explicitly labeled as adaptations of the authors' own synchronous protocols [3,4], which is honest. The blockchain oracle application is a nice motivation and gives a clear statement of how Download improves per-peer query cost from O(mn) to O(mn/k).\n\nThe problem is Lemma 11. Claim 10 says at the start of phase p a peer has at most n(f/k)^p unknown bits. At the termination phase p = log_{k/f}(n/k), that is k bits, not 1 as Lemma 11 uses. The final direct query must cover all remaining unknowns, so you get an additive k, and the query bound becomes O(n/(γk) + k), which is not O(n/(γk)) when n = o(k^2). That is a load-bearing gap for the headline crash result. It is not necessarily fatal: running to log_{k/f}(n) phases leaves one unknown bit and the geometric sum is still O(n/(γk)); the time analysis would need redoing, but the repair looks mechanical. As written though, the optimality claim is unsupported. I did not find a similar issue in the Byzantine sections; those appear sound.\n\nWho is this for: people working on the DR model, distributed retrieval from external sources, or oracle protocols. It is the first asynchronous treatment, so it is a useful reference even if the crash theorem needs a fix. It deserves a serious referee, with a request for a corrected Lemma 11 before the complexity claim is accepted.","headline":"First asynchronous treatment of the Data Retrieval model, with a genuinely new crash protocol and a neat randomized Byzantine lower bound, but the main crash result has a proof gap around leftover unknown bits that should be fixed before the optimality claim is trusted.","tokens_in":23147,"tokens_out":2731,"would_cite":true,"duration_ms":28240,"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":"A deterministic protocol solves async download with optimal per-peer query cost","keywords":["distributed data retrieval","download problem","asynchronous networks","crash faults","Byzantine faults","query complexity","blockchain oracles","decision trees"],"falsifier":"Simulate the crash protocol (Algorithm 2) with concrete parameters, e.g. k=100, f=40, n=1000, run it for P=log_{k/f}(n/k) phases, and count the unknown bits a nonfaulty peer must query in the termination step. Claim 10 predicts roughly n(f/k)^P = k = 100 unknown bits per peer; Lemma 11 requires n/k·(f/k)^P = 1. A direct count decides which bound governs, and thus whether Q is O(n/(γk)) or O(n/(γk)+k).","tokens_in":22315,"feed_emoji":"📡","tokens_out":8546,"duration_ms":92507,"temperature":0.7,"pith_summary":"This paper asks whether k peers connected by an asynchronous network can jointly learn an n-bit array held by a trusted but expensive external source, when some peers may fail. It answers yes for crash faults: a deterministic protocol lets every nonfaulty peer learn the whole array with O(n/((1−β)k)) expensive lookups to the source, matching the no-failure ideal of n/k up to a constant that depends on the crash fraction, for any fraction β<1. For Byzantine faults the paper draws a line at β=1/2: at or above that fraction, even randomized protocols force some honest peer to query more than n/2 bits, whereas below it a randomized protocol attains near-optimal query complexity. These protocols are also applied to blockchain oracles, reducing the per-node cost of collecting off-chain data from O(mn) to roughly O(mn/k). The headline is the crash result: it shows the \"learn everything from the source\" task, unlike agreement or broadcast, is deterministically solvable in asynchrony without sacrificing query balance.","feed_headline":"Async download stays query-optimal when a fraction of peers crash","feed_subtitle":"A deterministic protocol splits an n-bit file among peers so each surviving peer asks for only about n/((1−β)k) bits, with no global clock.","key_machinery":"Crash protocol: a sequence of phases, each with an assignment function σ_p mapping every bit of X to the peer responsible for querying it. In stage 1 each peer queries its assigned unknown bits and broadcasts them; in stage 2 each peer waits for k−f replies and reports which peers it has not heard from; in stage 3 the unknown bits of missing peers are redistributed evenly among all peers. Because at most f of the k assignments fail to arrive, the number of bits any peer still lacks is multiplied by at most f/k per phase, and after P=log_{k/f}(n/k) phases the residual is small enough to query directly. Byzantine protocols: parties partition X into segments, each peer broadcasts the segment it","core_discovery":"The paper's central claim is a threshold split for the Download problem in asynchronous networks. Under crash faults, it claims a deterministic protocol that solves Download for any f<k crashes with per-peer query complexity Q=O(n/(γk)), where γ=1−f/k, time O(n/ϕ + log_{k/f}(ϕ)), and message complexity O(nk²); because the no-failure load is Θ(n/k), this is optimal up to the 1/γ factor. Under Byzantine faults, it claims that for β≥1/2 every randomized protocol has an execution where some peer queries more than n/2 bits, and every deterministic protocol requires Q=n; for β<1/2 it claims a two-cycle randomized protocol with Q=O(√(n/(γ−β)) + n log n/((γ−β)k)) and a multi-cycle one with expected","pith_inferences":["The strict O(n/(γk)) statement in the crash protocol rests on Lemma 11's claim that the termination phase costs one bit per peer; the paper's own Claim 10 bounds the leftover by k bits per peer at that point, so a charitable reading is Q=O(n/(γk)+k), which is only clearly optimal when n=Ω(k²). That reconciliation is my inference, not the paper's claim.","The f/k geometric-decay template should transfer to other retrieve(f) problems: any function computed locally after downloading X inherits the same per-peer query bound, so the result generalizes beyond the identity function.","The Byzantine β=1/2 threshold suggests a natural test in the barely-minority regime: run the two-cycle protocol with β just below 1/2 and ask whether the √n term is essential or an artifact of the segment-size choice; the paper does not resolve that tradeoff.","The protocol assumes queries to a source return stable, identical values to different peers; if data can change between queries, the reassignment logic breaks, and a plausible necessary condition is snapshot-consistent reads rather than plain read-only access."],"forward_implications":["Any fixed fraction β<1 of crash faults can be tolerated with per-peer query cost O(n/((1−β)k)), the same order as the ideal synchronized no-failure protocol.","Download is solvable deterministically in asynchrony without using reliable broadcast or consensus as a building block, in contrast to classic agreement-style impossibilities.","For Byzantine settings with β≥1/2, randomization cannot reduce the query burden below a constant fraction of n, so the synchronous randomized speedup disappears.","For β<1/2, randomized asynchronous protocols achieve near-optimal expected query complexity, making the synchronous randomized results portable to asynchronous networks.","Blockchain oracle data collection can be load-balanced across peers: the per-node query cost for m data sources drops from O(mn) to roughly O(mn/k), provided the data source is stable across queries."],"supporting_citations":[{"why":"Introduces the DR model and the Download problem; its synchronous committee-based Byzantine protocol is the template the paper adapts to asynchrony.","marker":"[3]"},{"why":"The companion paper's randomized synchronous Download protocols supply the two-cycle and multi-cycle structures that the asynchronous Byzantine algorithms modify.","marker":"[4]"},{"why":"Chainlink OCR, one of the blockchain-oracle protocols whose data-collection step the Download-based ODC process improves.","marker":"[11]"},{"why":"DORA, another oracle protocol used to define the Oracle Data Collection abstraction and its baseline query cost.","marker":"[15]"},{"why":"The FLP impossibility result motivates why deterministic termination under asynchrony is non-trivial and why the Download protocol's determinism is notable.","marker":"[19]"}],"fun_headline_variants":["No clock needed: optimal async download survives crashes","Async download: query-optimal even with fraction of crashes","First async download protocol: optimal queries under crashes","Byzantine async download: lower bound at half, randomized below","Crash-tolerant async download matches optimal query load"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The optimal crash protocol's query bound depends on the claim that after the last reassignment phase a peer has only one remaining unknown bit to query; the paper's own phase-by-phase count leaves about k unknown bits per peer at that point, so the strict O(n/(γk)) conclusion needs the geometric decay count to be tightened.","fun_headline_variants_meta":{"raw":{"variants":["No clock needed: optimal async download survives crashes","Async download: query-optimal even with fraction of crashes","First async download protocol: optimal queries under crashes","Byzantine async download: lower bound at half, randomized below","Crash-tolerant async download matches optimal query load"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000765,"raw_usage":{"total_tokens":3303,"prompt_tokens":893,"completion_tokens":2410,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":637,"completion_tokens_details":{"reasoning_tokens":2343}},"tokens_in":637,"tokens_out":2410,"duration_ms":16824,"temperature":1.0,"reasoning_tokens":2343,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T10:43:31.332157+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the crash protocol (Algorithm 2) with concrete parameters, e.g. k=100, f=40, n=1000, run it for P=log_{k/f}(n/k) phases, and count the unknown bits a nonfaulty peer must query in the termination step. Claim 10 predicts roughly n(f/k)^P = k = 100 unknown bits per peer; Lemma 11 requires n/k·(f/k)^P = 1. A direct count decides which bound governs, and thus whether Q is O(n/(γk)) or O(n/(γk)+k).","supporting_citations":[{"cited_title":"Byzantine Resilient Distributed Computing on External Data","cited_arxiv_id":null,"evidence_quote":"Introduces the DR model and the Download problem; its synchronous committee-based Byzantine protocol is the template the paper adapts to asynchrony."},{"cited_title":"Distributed Download from an External Data Source in Byzantine Majority Settings","cited_arxiv_id":null,"evidence_quote":"The companion paper's randomized synchronous Download protocols supply the two-cycle and multi-cycle structures that the asynchronous Byzantine algorithms modify."},{"cited_title":"Chainlink off-chain reporting protocol","cited_arxiv_id":null,"evidence_quote":"Chainlink OCR, one of the blockchain-oracle protocols whose data-collection step the Download-based ODC process improves."},{"cited_title":"DORA: Distributed Oracle Agreement with Simple Majority","cited_arxiv_id":"2305.03903","evidence_quote":"DORA, another oracle protocol used to define the Oracle Data Collection abstraction and its baseline query cost."},{"cited_title":"Fischer, Nancy A","cited_arxiv_id":null,"evidence_quote":"The FLP impossibility result motivates why deterministic termination under asynchrony is non-trivial and why the Download protocol's determinism is notable."}],"review_version":1}