Pith. sign in

REVIEW 3 major objections 5 minor 14 references

Distributed Download from an External Data Source in Faulty Majority Settings

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A randomized protocol downloads an n-bit array at near-optimal per-peer query cost even when almost all peers are Byzantine.

desk verdict 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. read the letter →

arxiv 2412.19649 v1 pith:SWK5ZKJK submitted 2024-12-27 cs.DC cs.DS

John Augustine , Soumyottam Chatterjee , Valerie King , Manish Kumar , Shachar Meir , David Peleg This is my paper · ORCID
classification cs.DCcs.DS MSC 68M1468W1568W20
keywords distributeddownloaddataretrievalmodelByzantinefaultsquerycomplexityblacklistingcrashbroadcastrandomizedalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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}$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [§6.2, Lemma 6.11 and Theorem 6.12] 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.
  2. [§3, Lemma 3.3 and Theorem 3.6] 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.
  3. [§4.3, Corollary 4.7] 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 ilde O notation consistently.
minor comments (5)
  1. [§3, opening paragraph] 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.
  2. [§2, Theorem 2.5] 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.
  3. [Table 2, Theorem 6.4 row] 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.
  4. [§6.2, paragraph after Lemma 6.11] 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.
  5. [§7, first paragraph] The word "Retervial" in "Data Retervial model" is a typo for "Retrieval."

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the main protocols are derived from first principles, with only non-load-bearing self-citations to the authors' prior work.

full rationale

The paper's derivation chain is self-contained. Theorem 2.5 and Algorithm 1 are proven in Section 2 using the stated adversary model, Chernoff bounds, and union bounds; the comparison to [3] is descriptive rather than load-bearing, and the theorem does not depend on [3]'s proofs. The lower bound in Section 3 is an indistinguishability argument built from the paper's own definitions. The faster protocols in Section 4 are analyzed with Chernoff bounds and explicit decision-tree constructions, again without relying on any external or prior result for correctness. The crash-fault algorithms in Sections 5 and 6 are deterministic and their correctness proofs are self-contained; citations to [2] and [10] are standard background, not circular support. The only author-overlap self-citations are to [3] as a baseline and to [2] for the primary-backup idea, and neither carries the central argument. I therefore find no step that reduces by construction, by fitted parameter, or by a self-citation chain to its own inputs. One non-circular correctness concern should be flagged: Section 6.2's claimed O(n) asynchronous time bound relies on the assertion that "after 1 time unit, every message is delivered (even by slow peers)", whereas the model states that "an adversary may delay every message by any finite amount of time". This is a soundness gap in the time analysis, not a circularity, and it does not raise the circularity score.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The central claims rest only on the stated model assumptions (synchronous or asynchronous rounds, correct external source, bounded Byzantine fraction, adversary limited to past randomness) and standard probabilistic inequalities. No hidden free parameters are fitted to data; δ is a universal constant fixed by the error-probability analysis.

free parameters (1)
  • δ (Algorithm 1 threshold constant)
    Universal constant chosen in Lemmas 2.2 and 2.4 to satisfy error-probability inequalities; not fitted to data.
assumptions (6)
  • domain assumption Synchronous rounds consist of query, response, and message-passing sub-rounds.
    The protocols and complexity measures in Sections 2 and 4 are built on this three-stage round structure from Section 1.1.
  • domain assumption The external source returns the correct bit for every Query(i).
    All gossip-learning and decision-tree arguments assume queried bits are authoritative, as stated in Section 1.1.
  • domain assumption The adversary chooses Byzantine peers at the start of each round and does not see the current round's fresh random coins.
    Section 1.1 limits adversary knowledge to random bits generated up to round t-1; the Chernoff arguments in Section 2 depend on the freshness of this randomness.
  • domain assumption At most βk peers are faulty at any time, leaving γk honest peers.
    All thresholds (e.g., t = γk/(2K) and ν·2^j in Section 2) are computed from this lower bound on honest peers.
  • domain assumption Peers have unique IDs in [1,k].
    Used for leader selection and round-robin schedules in Sections 5 and 6, and for message addressing in the clique network.
  • standard math Chernoff and union bounds.
    Used throughout Sections 2, 4, and 6 to establish high-probability claims.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Distributed Download from an External Data Source in Faulty Majority Settings." pith.science (2026). https://pith.science/paper/SWK5ZKJK

@misc{pith2026241219649,
  author       = {Pith},
  title        = {Pith review of: Distributed Download from an External Data Source in Faulty Majority Settings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SWK5ZKJK}},
  note         = {Machine review of arXiv:2412.19649}
}
abstract

We extend the study of retrieval problems in distributed networks, focusing on improving the efficiency and resilience of protocols in the \emph{Data Retrieval (DR) Model}. The DR Model consists of a complete network (i.e., a clique) with $k$ peers, up to $\beta k$ of which may be Byzantine (for $\beta \in [0, 1)$), and a trusted \emph{External Data Source} comprising an array $X$ of $n$ bits ($n \gg k$) that the peers can query. Additionally, the peers can also send messages to each other. In this work, we focus on the Download problem that requires all peers to learn $X$. Our primary goal is to minimize the maximum number of queries made by any honest peer and additionally optimize time. We begin with a randomized algorithm for the Download problem that achieves optimal query complexity up to a logarithmic factor. For the stronger dynamic adversary that can change the set of Byzantine peers from one round to the next, we achieve the optimal time complexity in peer-to-peer communication but with larger messages. In broadcast communication where all peers (including Byzantine peers) are required to send the same message to all peers, with larger messages, we achieve almost optimal time and query complexities for a dynamic adversary. Finally, in a more relaxed crash fault model, where peers stop responding after crashing, we address the Download problem in both synchronous and asynchronous settings. Using a deterministic protocol, we obtain nearly optimal results for both query complexity and message sizes in these scenarios.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages

  1. [3]

    Byzantine Resilient Distributed Computin g on External Data

    John Augustine, Jeffin Biju, Shachar Meir, David Peleg, S rikkanth Ramachandran, and Aishwarya Thiruvengadam. Byzantine Resilient Distributed Computin g on External Data. In Dan Alistarh, ed- itor, 38th International Symposium on Distributed Computing (DI SC 2024) , volume 319 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 3:1–3:23, D...

    work page 2024

  2. [1]

    Balanced byzantine reliable broadcast with near-op timal communication and improved com- putation

    Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayan k V aria, Zhuolun Xiang, and Haibin Zhang. Balanced byzantine reliable broadcast with near-op timal communication and improved com- putation. In Proceedings of the 2022 ACM Symposium on Principles of Distr ibuted Computing , PODC’22, page 399–417, New Y ork, NY , USA, 2022. Association for Computing...

    work page 2022

  3. [2]

    Alsberg and John D

    Peter A. Alsberg and John D. Day. A principle for resilien t sharing of distributed resources. In Proceedings of the 2nd International Conference on Softwar e Engineering, ICSE ’76, page 562–570, Washington, DC, USA, 1976. IEEE Computer Society Press

    work page 1976

  4. [4]

    Byzantine agreement and leader election: From classical to the modern

    John Augustine, Anisur Rahaman Molla, and Gopal Pandura ngan. Byzantine agreement and leader election: From classical to the modern. In ACM PODC, pages 569–571, 2021

    work page 2021

  5. [5]

    Asynchronous byzantine agreement prot ocols

    Gabriel Bracha. Asynchronous byzantine agreement prot ocols. Information & Computation, 75:130– 143, 1987

    work page 1987

  6. [6]

    Chainlink off- chain reporting protocol

    Lorenz Breidenbach, Christian Cachin, Alex Coventry, A ri Juels, and Andrew Miller. Chainlink off- chain reporting protocol. Technical report, Chainlink Lab s, 2021

    work page 2021

  7. [7]

    Practical byzantine f ault tolerance

    Miguel Castro and Barbara Liskov. Practical byzantine f ault tolerance. In 3rd Symp. on Operating Systems Design and Implementation , OSDI, page 173–186. USENIX Assoc., 1999

    work page 1999

  8. [8]

    DORA: distributed oracle agreement with simple majority

    Prasanth Chakka, Saurabh Joshi, Aniket Kate, Joshua Tob kin, and David Y ang. DORA: distributed oracle agreement with simple majority. CoRR, abs/2305.03903, 2023

    arXiv 2023

Show all 14 references
  1. [9]

    Dolev and H

    D. Dolev and H. R. Strong. Authenticated algorithms for b yzantine agreement. SIAM J. Computing , 12(4):656–666, 1983

    1983

  2. [10]

    Fischer, Nancy A

    Michael J. Fischer, Nancy A. Lynch, and Michael S. Pater son. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382, apr 1985

    1985

  3. [11]

    Th e byzantine generals problem

    Leslie Lamport, Robert Shostak, and Marshall Pease. Th e byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401, jul 1982. 38

    1982

  4. [12]

    Pease, R

    M. Pease, R. Shostak, and L. Lamport. Reaching agreemen t in the presence of faults. J. ACM , 27(2):228–234, apr 1980

    1980

  5. [13]

    Michael O. Rabin. Randomized byzantine generals. In 24th FOCS, pages 403–409, 1983

    1983

  6. [14]

    R. L. Rivest, A. Shamir, and L. Adleman. A method for obta ining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120–126, feb 1978. 39

    1978

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.