{"id":"4330bbca-cf4a-4f47-9d73-ecb0468c7c51","arxiv_id":"2504.17471","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A gossip learning framework with history-aware peer sampling and an adaptive aggregation threshold keeps accuracy within about 5% of the no-attack baseline when 30% of nodes are Byzantine.","lead":"GRANITE protects gossip learning, where computers train by exchanging models with neighbors, against attackers who both poison models and flood the peer sampling layer with fake identifiers. It does this by remembering all peers seen over time and adapting how many suspicious models to filter each round.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The exponential-decay proof assumes honest push/pull arrival rates that do not hold during flooding; the worst-case B(t) bound is therefore unsupported.","rationale":"The reader's weakest_assumption identifies the same core issue: the mean-field ODE in Eq. (5) assumes honest identifiers arrive at a constant rate alpha, with alpha_push computed as if an honest node is still selected as a push target with probability roughly 1/(n-1) even when views are flooded. My analysis confirms this is load-bearing: the exponential decay of B(t) is the basis for the APT threshold, and if alpha is not a worst-case lower bound, Corollary V.2 and Lemma V.3 do not establish the claimed high-probability correctness of robust aggregation under the stated threat model. The concern is not that the empirical results are dishonest or fabricated; the experiments appear credible and the framework may work in practice. The concern is that the formal guarantee exceeds what the proof supports. The paper's own Figure 5 shows a large gap between B(t) and fin, which the authors attribute to conservativeness, but this does not address the possibility that alpha itself is optimistic in the flooded regime. A concrete simulation measuring actual honest-ID arrival rates under F = infinity, and comparing the realized Byzantine fraction against the ODE prediction, would settle whether the exponential-decay claim is quantitatively valid. Because the central theoretical claim is conditional on this unverified rate assumption, the appropriate verdict remains CONDITIONAL: the paper should either provide a rigorous worst-case lower bound on alpha (or a state-dependent ODE) or explicitly reclassify the exponential-decay and APT guarantees as heuristic and support them with sensitivity analysis. The secondary issue of B being known as a system parameter, while real, is less central because the authors note it can be set conservatively as an upper bound; the alpha problem is the sharper, more fundamental gap.","tokens_in":20126,"tokens_out":5534,"duration_ms":59331,"concrete_test":"Simulate HaPS with n = 300, v = 20, f = 0.3, and F = infinity for 100 rounds, and measure the per-round honest-ID arrival rate alpha_emp(t) received by honest nodes (unique honest identifiers added to histories via push and pull). Compare alpha_emp(t) with the constant alpha used in Eq. (5). Then solve the ODE with alpha replaced by the empirical arrival rate and check whether the realized Byzantine fraction in honest views stays below the recomputed B(t) curve at every round. If the empirical honest-ID arrival rate is materially below the assumed alpha (e.g., by more than 2x) in the early flooded rounds, and the empirical fin exceeds the recomputed B(t), then the exponential-decay claim fails in exactly the worst-case regime it is intended to cover, and the APT thresholds derived from it are not justified.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The formal centerpiece is Corollary V.2, which states B(t) = B / (B + |H| - (|H| - C(0)) exp(-alpha/|H| t)). This rests on the ODE in Eq. (5), dC/dt = alpha * (|H| - C(t))/|H|, with alpha = alpha_pull + alpha_push. The push term alpha_push is computed as (|H|/(n-1)) * (C(0)/(C(0)+B)) * v. This assumes that each honest node selects its push recipient uniformly among all n-1 nodes and that the honest fraction in the sender's view is C(0)/(C(0)+B). Under the paper's own flooded worst case (F = infinity), neither holds: an honest node's view is dominated by Byzantine identifiers, so the probability that a push from an honest node reaches an honest recipient is far below 1/(n-1), and the expected number of honest identifiers carried by each such push is also lower than v * C(0)/(C(0)+B). Similarly, alpha_pull = (C(0)/(C(0)+B))^2 * v assumes the pulled view has honest fraction C(0)/(C(0)+B), whereas flooding can push the actual Byzantine fraction far above this value in early rounds (Figure 5 shows initial fin around 32% for f = 0.3, and the gap is larger for F = infinity). Consequently, alpha is not a conservative lower bound on honest-ID arrivals; it is a mean-field estimate for a non-flooded regime. If alpha is optimistic, C(t) grows faster than guaranteed, B(t) decays too quickly in the analysis, and the APT threshold b(t) = (1+delta) v B(t) is too small. Lemma V.3's Chernoff guarantee is conditioned on each view slot being independently Byzantine with probability at most B(t), a premise inherited from the same overoptimistic bound. The paper itself acknowledges in the Practical Consideration that the fallback b(t) = min(b(t), v-1) is 'not theoretically backed by the Chernoff bound,' which further indicates the formal guarantee has a gap. The secondary assumption that the total Byzantine count B is known as a system parameter also weakens the practical force of the guarantee, but the rate-alpha problem is the more load-bearing issue.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GRANITE, a gossip learning framework designed to resist Byzantine nodes that simultaneously poison models and manipulate the underlying random peer sampling protocol. GRANITE consists of HaPS, a history-aware peer sampling protocol that maintains a growing set of encountered identifiers, and APT, an adaptive probabilistic thresholding mechanism that sets the filtering threshold of a robust aggregator from a time-dependent estimate B(t) of the Byzantine fraction in local views. The authors derive an exponential decay formula for B(t) from a mean-field ODE, use this in a Chernoff-based threshold computation, and evaluate the framework on MNIST and Purchase100 under FOE and ALIE poisoning attacks combined with flooding attacks, comparing against BASALT and several robust aggregators. The paper claims convergence within 5% of non-Byzantine accuracy under 30% Byzantine nodes, faster convergence, and up to 9x lower communication cost compared with the connectivity requirements of existing robust gossip theory.","tokens_in":20593,"tokens_out":6225,"duration_ms":67098,"significance":"If the theoretical claims were fully supported, this would be a valuable contribution: it targets a realistic combined threat model that attacks both model aggregation and peer sampling, and it proposes a concrete mechanism for adapting aggregation thresholds in dynamic graphs. The empirical study is a genuine strength: it uses two datasets, two strong poisoning attacks, flooding at several strengths, comparisons with BASALT, multiple robust aggregators, and released code, and the reported convergence behavior appears credible. However, the formal centerpiece is not yet established: the exponential-decay bound in Corollary V.2 relies on arrival rates that are not worst-case lower bounds under flooding, and the APT guarantee in Lemma V.3 rests on independence assumptions that the protocol does not provide. These are load-bearing issues for the advertised formal guarantees, so the paper needs substantial revision rather than minor polishing.","major_comments":[{"comment":"The derivation of alpha_push is not a conservative lower bound under the paper's own flooding model. Algorithm 1 (lines 6-7) has each honest node select a push recipient uniformly from its current view Nout(i)_{t-1}, not uniformly from all n-1 nodes. Under a flooding attack, an honest node's view can be dominated by Byzantine identifiers, so the probability that an honest push message reaches an honest recipient is far smaller than |H|/(n-1). The expression alpha_push = (|H|/(n-1)) * (C(0)/(C(0)+B)) * v therefore overestimates the true rate at which honest identifiers arrive via push messages in the flooded regime. Since Eq. (5) is the basis for Theorem V.1 and Corollary V.2, the claim that B(t) is a conservative upper bound on the Byzantine fraction is not supported by the proof as written.","section":"Section V.B.2, Eq. (5)"},{"comment":"The Chernoff argument assumes that each of the v view slots is independently Byzantine with probability at most B(t). However, view slots in HaPS are produced by min-wise independent permutations over a shared history, so they are not independent in general, and B(t) is an upper bound on the expected Byzantine fraction rather than a per-slot probability. The lemma therefore does not provide the stated high-probability guarantee for the actual protocol. The authors should either prove a suitable concentration bound under the protocol's sampling mechanism, or explicitly weaken Lemma V.3 to a heuristic statement.","section":"Section V.C, Lemma V.3"},{"comment":"The fallback that caps b(t) at v-1 is explicitly described as not backed by the Chernoff bound. This cap can bind precisely in early rounds, when B(t) is largest and the Byzantine presence in views is highest, so the high-probability correctness claim for robust aggregation does not extend to the regime where the cap is active. The formal claims should be scoped to the regime where the uncapped threshold applies, or the cap needs its own analysis.","section":"Section V.C, Practical Consideration"},{"comment":"The 'communication cost multiplicative gain' compares a theoretical worst-case filtering threshold from the static-graph analysis of Gaucher et al. with GRANITE's empirical threshold b(t)<=19. Since the paper explicitly leaves 'extending theoretical convergence guarantees for GRANITE' to future work, the abstract's claim of operating on graphs 'up to 9x lower communication cost' is an empirical observation rather than a theoretically established property. This should be stated more carefully so as not to imply a proven robustness guarantee at these graph densities.","section":"Section VII.B, Table III"}],"minor_comments":[{"comment":"The worst-case scenario assumes every honest node's history already contains all Byzantine identifiers, while the initialization assumption in Section IV.B says the bootstrap set is sampled i.i.d. with initial Byzantine fraction f; please clarify how these two assumptions are reconciled and how C(0) is determined in the theorem.","section":"Section V.B.2"},{"comment":"The text says 'for F = 0.1' when discussing Figures 1b and 2b; this should be f = 0.1, since F denotes the flooding force.","section":"Section VII.A"},{"comment":"The table lists the same symbol Nout(i)t for both outgoing and incoming neighbors; the incoming neighbor notation should be distinct, presumably Nin(i)t, and the definition should match the usage in the body.","section":"Table I"},{"comment":"The caption and text refer to B(t) as a 'higher bound' and to 'the higher bound approximation'; this should be 'upper bound' throughout.","section":"Section VII.D and Figure 5"},{"comment":"The abstract's 'within 5% of non-Byzantine accuracy' claim is not directly visible in the figures, which plot F1-Score against an 'optimal' curve; please specify explicitly where this 5% figure is measured and how it is computed.","section":"Abstract and Section VII"},{"comment":"The evaluation section does not state the number of independent runs or seeds used; since standard deviations are reported in the text, please specify the experimental repetitions used to compute them.","section":"Section VI.A"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead GRANITE. Worth your time if you work on decentralized learning or Byzantine-resilient gossip. The paper identifies a genuinely unaddressed problem: existing BRPS protocols like BASALT bound Byzantine influence on average, but robust aggregators like Clipped Summation need per-round control over the Byzantine fraction in local views. Flooding the peer-sampling layer breaks that. GRANITE's answer is a history-aware sampling scheme with min-wise rank functions plus an adaptive threshold that uses an estimated Byzantine ratio to set the aggregator's clipping parameter. The empirical work is solid: MNIST and Purchase100, two strong poisoning attacks, flooding at F=1,2,∞, comparison against BASALT, and a clear demonstration that BASALT diverges while GRANITE stays within a few percent of clean accuracy at 30% Byzantine nodes. The 9x communication cost reduction over the theoretical requirement is well argued. Code is public. Credit where due: the dual-attack threat model and the HaPS+APT combination are new, and the experimental campaign is credible.\n\nNow the soft spot, and it's not minor. The formal centerpiece, Corollary V.2 (exponential decay of B(t)), is derived from an ODE whose arrival rate alpha is a mean-field estimate for the non-flooded case. The push term assumes an honest node selects its push recipient uniformly among all n-1 nodes and that the honest fraction in the sender's view is C(0)/(C(0)+B). Under the paper's own flooded worst case, F=∞, an honest node's view is dominated by Byzantine IDs, so the probability the push reaches an honest recipient is far below 1/(n-1), and the pulled view likewise has a Byzantine fraction higher than the assumed honest fraction. Alpha is therefore not a conservative lower bound on honest-ID arrivals; it's an optimistic estimate. That means B(t) decays too fast in the analysis, and the APT threshold b(t) may be smaller than the true Byzantine count in a view. The paper's own 'Practical Consideration' admits the fallback min(b(t), v-1) is 'not theoretically backed by the Chernoff bound.' The assumption that the total Byzantine count B is known as a system parameter is a secondary weakness; it's a common assumption but worth stating more carefully.\n\nDoes this kill the paper? No. The empirical B(t) curve in Figure 5 sits above the measured fin, so the bound appears to hold in practice for the tested settings, and the system clearly works. But the formal claims as written outrun the proof. A serious revision should either (i) prove a conservative lower bound on alpha under flooding, perhaps using the fact that Byzantine nodes can only send Byzantine IDs and history grows monotonically, or (ii) state the decay as an empirical observation and drop 'formal analysis' from the contribution list.\n\nWho is this for? Researchers in decentralized/federated learning who care about adversarial networking layers. It deserves a serious referee: the problem is real, the system is plausible, and the experiments are reproducible. I'd send it to peer review with the expectation of major revision focused on the theory. Not a desk reject.\n\nRecommendation: accept as a conditional after theory is fixed or softened.","headline":"Useful systems paper with a real dual-attack threat model and strong empirical results, but the exponential-decay proof rests on a mean-field arrival rate that ignores flooding, so the formal claims outrun the analysis.","tokens_in":21158,"tokens_out":4330,"would_cite":true,"duration_ms":42838,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"GRANITE claims that gossip learning can stay accurate with up to 30% Byzantine nodes by tracking encountered identifiers and adaptively filtering poisoned models, with the local Byzantine ratio decaying exponentially to the global fraction.","keywords":["gossip learning","Byzantine resilience","random peer sampling","model poisoning","robust aggregation","dynamic graphs","adaptive threshold","flooding attack"],"falsifier":"Measure the empirical Byzantine fraction in honest local views ($f_{in}(t)$) during the first 50 rounds under $F=\\infty$ flooding with $f=0.3$. The exponential-decay claim predicts $f_{in}(t)$ falls from its early spike toward roughly $f$ within about 20 rounds; if it stays materially above $f$ after the warm-up phase, the claim fails. A more mechanistic check is to instrument the arrival rate of honest identifiers $\\alpha$ and verify that the growth of unique honest identifiers follows $dC(t)/dt = \\alpha(|H|-C(t))/|H|$; a mismatch under flooding would falsify the ODE.","tokens_in":19917,"feed_emoji":"🛡️","tokens_out":7628,"duration_ms":67585,"temperature":0.7,"pith_summary":"Gossip learning is a fully decentralized training scheme whose dynamic-graph variants rely on random peer sampling, and GRANITE tackles the attack that previous defenses missed: Byzantine nodes that poison models and simultaneously flood the peer-sampling layer with their identifiers. The paper's central claim is that this dual attack can be neutralized by giving each node a growing history of all identifiers it has encountered and using hash-based ranking to fill view slots, so the expected fraction of Byzantine nodes in local views decays exponentially to the global fraction $f$. On top of this, an adaptive probabilistic threshold converts the decaying estimate into a per-round filtering count for robust aggregators such as clipped summation and geometric trimmed summation. If these claims hold, gossip learning can stay accurate within about 5% of the non-Byzantine optimum under 30% Byzantine nodes while using up to 9 times sparser communication graphs than current theory demands.","feed_headline":"Gossip learning keeps accuracy under 30% Byzantine attackers","feed_subtitle":"History-aware peer sampling drives Byzantine views down exponentially, enabling sparse, dynamic graphs","key_machinery":"The machine that carries the argument is the pair (HaPS, APT). HaPS maintains, at every node, a history of every identifier it has ever received via push and pull exchanges; each of the $v$ view slots then selects the minimum under an independent ranking hash, so Byzantine flooding only adds identifiers that tend to lose the hash-based ranking against the accumulating honest history. The formal engine is the mean-field ODE $dC(t)/dt = \\alpha(|H|-C(t))/|H|$ for the expected number of unique honest identifiers known, whose solution gives the exponential decay $B(t)$ of the expected Byzantine fraction in local views. APT then turns that decay into a concrete filtering budget: the Chernoff upper-tail inequality $P(X_t \\ge (1+\\delta)vB(t)) \\le \\exp(-\\delta^2 vB(t)/(\\delta+2))$ is inverted to find the smallest $\\delta$ for failure probability $\\kappa$, yielding $b(t)=(1+\\delta)vB(t)$ capped at $v-1$. This is the identity that lets a robust aggregator designed for a static, bounded fraction of Byzantine neighbors keep its guarantee in a dynamic graph where the Byzantine density is initially high and then recedes.","core_discovery":"Under GRANITE, each node's local view is refreshed from a monotonically growing history $h_i(t)$ using slot-specific ranking functions, so that a flood of Byzantine identifiers cannot permanently crowd out honest ones. Modeling the growth of the number of known honest identifiers $C(t)$ by the mean-field ODE $dC(t)/dt = \\alpha(|H|-C(t))/|H|$, the paper obtains $C(t)=|H|-(|H|-C(0))\\exp(-\\alpha t/|H|)$ and hence the Corollary V.2 bound $B(t)=B/(B+|H|-(|H|-C(0))\\exp(-\\alpha t/|H|))$, i.e., the expected Byzantine fraction in local views decays exponentially to $f$ even for adversaries with unlimited flooding capability. This bound feeds an adaptive probabilistic threshold: treating each view slot as independently Byzantine with probability at most $B(t)$ and applying a Chernoff upper-tail bound, the node chooses the smallest $\\delta>0$ such that $P(X_t \\ge (1+\\delta)vB(t)) \\le \\kappa$ and sets the filtering threshold $b(t)=\\min((1+\\delta)vB(t), v-1)$. The paper claims this gives robust aggregators a bounded per-round adversarial presence with probability at least $1-\\kappa$, and that empirically GRANITE with CS or GTS converges to near-optimal F1 under FOE and ALIE attacks with up to 30% Byzantine nodes, whereas a state-of-the-art Byzantine-resilient peer sampling protocol diverges.","pith_inferences":["Editorial inference: the same $B(t)$-to-Chernoff pipeline should transfer to any robust aggregator with a known breakdown point, not just CS and GTS, making GRANITE a reusable robustness layer for decentralized optimization.","Editorial inference: the mean-field ODE assumes expectation-level arrivals; a stochastic-differential-equation version would reveal whether the exponential decay holds in probability and how large the early-round variance is, which is exactly the regime where the worst-case bound is loosest.","Editorial inference: feeding back the measured empirical Byzantine fraction in place of the theoretical $B(t)$ could relax the assumption that the total number of Byzantine nodes $B$ is known, at the price of losing the formal high-probability guarantee.","Editorial inference: because HaPS keeps every identifier ever seen, the protocol trades memory for robustness; the framework's practical ceiling is therefore set by how much stale honest history a node can store as the system grows."],"forward_implications":["With probability at least $1-\\kappa$ per round, the number of Byzantine models in a local view stays below $(1+\\delta)vB(t)$, so clipped summation and geometric trimmed summation retain their correctness guarantees in a dynamic graph.","The expected Byzantine fraction in any honest node's view converges to the global fraction $f$, removing the need to know the per-view Byzantine count $b$ that static robust gossip theory requires.","Robust learning becomes viable on sparse dynamic graphs: for $n=300$ with 30% Byzantine nodes, GRANITE keeps view size $v=20$ where the nominal theory for clipped summation would command more than 180 neighbors, giving up to a 9x reduction in messages.","GRANITE maintains honest-subgraph connectivity near 1 at $f=0.3$, where a state-of-the-art Byzantine-resilient sampling protocol loses connectivity for roughly 60% of honest nodes after 40 rounds.","The adaptive threshold filters most aggressively in early rounds, when flooding makes Byzantine presence highest, and aggregates more models later, giving faster convergence than fixed conservative thresholds."],"supporting_citations":[{"why":"Supplies the robust aggregators CS and GTS whose correctness GRANITE preserves and whose theoretical breakdown point sets the connectivity baseline.","marker":"[23]"},{"why":"BASALT is the state-of-the-art Byzantine-resilient peer sampling protocol that GRANITE compares against and shows to be insufficient for learning.","marker":"[31]"},{"why":"Brahms contributes the idea of sampling previously encountered identifiers with min-wise independent permutations, which HaPS extends.","marker":"[32]"},{"why":"Supplies the Chernoff upper-tail bound that APT uses to convert the estimated Byzantine density into a probabilistic filtering threshold.","marker":"[51]"},{"why":"Fall of Empires is one of the two model-poisoning attacks used to stress-test GRANITE.","marker":"[10]"},{"why":"A Little is Enough is the second model-poisoning attack used to stress-test GRANITE.","marker":"[11]"},{"why":"Establishes the exact-averaging and graph-size-independent convergence properties of dynamic gossip learning that GRANITE aims to preserve.","marker":"[7]"}],"fun_headline_variants":["GRANITE resists Byzantine peers with history-aware sampling","Gossip learning stays accurate under 30% Byzantine attack","Exponential decay of Byzantine influence in gossip learning","Robust gossip learning with adaptive thresholds and history","GRANITE: Byzantine-resilient learning on sparse dynamic graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that honest identifiers arrive at a constant rate $\\alpha$, which assumes that even under worst-case flooding a random push target is still selected approximately uniformly over all $n-1$ nodes; if flooding skews that selection toward Byzantine nodes, the exponential decay of $B(t)$ and the APT thresholds are not guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["GRANITE resists Byzantine peers with history-aware sampling","Gossip learning stays accurate under 30% Byzantine attack","Exponential decay of Byzantine influence in gossip learning","Robust gossip learning with adaptive thresholds and history","GRANITE: Byzantine-resilient learning on sparse dynamic graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000278,"raw_usage":{"total_tokens":1710,"prompt_tokens":1058,"completion_tokens":652,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":674,"completion_tokens_details":{"reasoning_tokens":572}},"tokens_in":674,"tokens_out":652,"duration_ms":5395,"temperature":1.0,"reasoning_tokens":572,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:40:07.301547+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure the empirical Byzantine fraction in honest local views ($f_{in}(t)$) during the first 50 rounds under $F=\\infty$ flooding with $f=0.3$. The exponential-decay claim predicts $f_{in}(t)$ falls from its early spike toward roughly $f$ within about 20 rounds; if it stays materially above $f$ after the warm-up phase, the claim fails. A more mechanistic check is to instrument the arrival rate of honest identifiers $\\alpha$ and verify that the growth of unique honest identifiers follows $dC(t)/dt = \\alpha(|H|-C(t))/|H|$; a mismatch under flooding would falsify the ODE.","supporting_citations":[{"cited_title":"Basalt: A rock-solid byzantine-tolerant peer sampling for very large decentral- ized networks,","cited_arxiv_id":null,"evidence_quote":"BASALT is the state-of-the-art Byzantine-resilient peer sampling protocol that GRANITE compares against and shows to be insufficient for learning."},{"cited_title":"Brahms: Byzantine resilient random membership sampling,","cited_arxiv_id":null,"evidence_quote":"Brahms contributes the idea of sampling previously encountered identifiers with min-wise independent permutations, which HaPS extends."},{"cited_title":"Exponential graph is provably efficient for decentralized deep training,","cited_arxiv_id":null,"evidence_quote":"Establishes the exact-averaging and graph-size-independent convergence properties of dynamic gossip learning that GRANITE aims to preserve."}],"review_version":1}