{"id":"e1ea28c0-e90f-4e80-aff9-72869ffc17c7","arxiv_id":"2501.13086","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In gossip networks, information quality at a node is the degradation Markov chain run for the hopcount of the fastest path, giving p^{Θ(AoI)} scaling for truthful-node fraction.","lead":"This paper studies gossip networks where nodes always keep the newest message and shows that message quality degrades with each hop, with the fraction of truthful nodes scaling like p to the power of the network's age of information. It gives exact scaling laws for fully connected and ring networks, linking lower age to slower misinformation spread.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's identification of quality with M0(H(i,n0)) fails when finite-rate source updates allow a newer packet to arrive via a non-geodesic path; the proof's survival coupling only tracks one packet.","rationale":"The reader identified the weakest point as the proof of Theorem 1: the argument that the freshest packet follows the first-passage path is sketched, not proved, and overwriting could break the hopcount identity. My stress-test agrees and sharpens the issue to a concrete failure. In a stream of source updates, the packet stored at a node is the one with the largest version number that has arrived, not necessarily the one on the minimal-delay geodesic. A later update can take a longer path and arrive after an earlier geodesic packet, becoming the stored packet; this changes the number of Markov transitions from H(i,n0) to a larger value. The two-path example has positive probability under the stated exponential clocks, so Theorem 1 is false as written for finite λe. The paper's proof considers a single packet in the reversed graph and never accounts for the source update process, so the gap is not merely formal. The reader's other concerns (the incorrect probability calculation in Lemma 1 and the omitted complete-graph adaptation) are real but secondary; even if those were fixed, the main theorem would still require an additional assumption or a different argument. Because Theorems 3 and 4 inherit the hopcount identity from Theorem 1, the paper's headline scaling laws are not established for the model as stated. I recommend REJECT rather than CONDITIONAL because the central claim admits a concrete counterexample within the stated model, not just an unproven step; a revision would need to either add and justify a continuous-source assumption or reformulate the quality dynamics.","tokens_in":7581,"tokens_out":22235,"duration_ms":251371,"concrete_test":"Simulate (or analytically compute) the two-path example: source S, nodes A,T,B,C; edges S-A and A-T with rates giving mean delays 1 each, and S-B, B-C, C-T with rates giving mean delay 1 each; source updates at finite rate λe. At a time t larger than the slower path delay, compare the empirical distribution of S_T(t) with p^{H(T,S)} for the two-state chain. If P(S_T(t)=T) differs from p^2 (or if S_T(t) takes the value M0(3) with positive probability), Theorem 1's identity fails. Repeat with λe large; only in the λe→∞ limit should the geodesic packet dominate.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim is Theorem 1, which asserts that at any time t the stored quality at node i is M0(H(i,n0)) once T(i,n0)≤t. The proof in Section III couples the age process to a single packet released at time 0 in the reversed graph, and asserts that the packet realizing the fastest path 'will survive.' In the actual model the source emits a stream of versions (Poisson rate λe) and nodes accept every newer packet regardless of the route it took. A later source update can therefore reach i along a path with strictly more hops than the minimizing path, and become the stored packet. Concretely, take two source-to-i paths: S-A-i with total delay 2 (2 hops) and S-B-C-i with total delay 3 (3 hops). Let version 1 be generated at time 0 and arrive at i at time 2 via the first path, and let version 2 be generated at time ε>0 and arrive at time 3+ε via the second path. At t=3+ε, node i stores version 2, a packet of hopcount 3, so Si(t) has positive probability of being M0(3), whereas H(i,n0)=2 and Theorem 1 predicts M0(2). The event has positive probability under the exponential clocks, so the claimed equality (even in distribution) is false without an additional assumption such as λe=∞. Since Theorems 3 and 4 are obtained by composing this identity with hopcount bounds, their p^{Θ(log n)} and p^{Θ(√n)} conclusions are not supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript introduces a model of information quality in gossip networks, in which each packet's quality evolves according to a discrete-time Markov chain as it is forwarded, and nodes always accept packets with a newer timestamp. The central claim, Theorem 1, is that the quality stored at node i at time t is either undefined or M0(H(i,n0)), where H(i,n0) is the hopcount of the first-passage path in a reversed auxiliary graph. Section IV specializes the Markov chain to a true/false misinformation model and states that the limiting proportion of truthful nodes is p^{Theta(log n)} for the complete graph and p^{Theta(sqrt n)} for the ring graph. The proof of Theorem 1 is presented as a coupling with a single packet in the reversed graph, and Lemma 1 is used to bound the ring hopcount.","tokens_in":7895,"tokens_out":17374,"duration_ms":208372,"significance":"If Theorem 1 were valid, it would be an attractive and useful reduction: information quality would be a function of the hopcount of the first-passage path, and all of the existing AoI hopcount machinery would transfer immediately to content quality. The two-state specialization gives crisp, falsifiable scaling predictions and a clear qualitative comparison between complete and ring graphs. The paper also has the merit of attempting to move beyond AoI to the actual content stored at nodes. However, the central identity is not established and, under the model as written, appears to be false; the later scaling results therefore do not follow. The potential significance is high, but the present manuscript does not support it.","major_comments":[{"comment":"The proof tracks a single packet and explicitly assumes that this packet is not overwritten, but overwriting by newer packets is a defining feature of the model in Section II.A: a node accepts every packet with a newer timestamp, regardless of the route it took. This is not a harmless technicality. Concretely, let S-A-i have total delay 2 and S-B-C-i have total delay 3. Suppose version 1 is generated at time 0 and reaches i at time 2 via S-A-i, and version 2 is generated at time epsilon and first reaches i at time 3+epsilon via S-B-C-i, because the source-to-A clock has not rung after epsilon. At that time i stores version 2, so Si(t)=M0(3) with positive probability, while H(i,n0)=2. This contradicts Eq. (3) even in distribution. The sentence 'assuming the packet is not overwritten at some point' is exactly the missing condition, and it is not guaranteed by the model. Since Theorems 3 and 4 are obtained by composing Eq. (3) with hopcount bounds, their p^{Theta(log n)} and p^{Theta(sqrt n)} conclusions are not supported by the current proof. A different model, such as a single packet with no subsequent source updates, would be needed for the statement as written.","section":"Section III, proof of Theorem 1 (after Eq. (8))"},{"comment":"The displayed probability computation is algebraically incorrect. For independent X ~ Exp(1) and Y ~ Exp(i/n), P(X<Y) = n/(n+i), not (n-i)/(n+1). Equation (15) is then used in Eq. (17) to compute the expected absorption time, so the claimed expected hopcount bound is not established by the argument as written. In addition, the transition probabilities in Eq. (12) do not match the boundary-clock probability computed in Eqs. (13)-(15); the claimed coupling between the Markov chain X(t) and the exploration of the auxiliary cycle is asserted rather than proved. It is possible that the Theta(sqrt n) conclusion can be salvaged with the correct probability, but the current proof does not do so.","section":"Lemma 1, Eqs. (13)-(15)"},{"comment":"The reduction of the complete-graph hopcount to Theta(log n) is not a proof. The text changes zero-weight source edges to Exp(1/n) edges and then rescales all edge weights by n, but it does not show that these operations preserve the hopcount or that the hypotheses of the result in [11] are satisfied by the resulting nonuniform edge-weight model. The sentence 'We omit the tedious details, as the proof follows almost verbatim from [11]' is not a substitute for the argument. Since Theorem 3 is one of the two main quantitative results, this is a load-bearing gap.","section":"Section IV, paragraph before Theorem 3"}],"minor_comments":[{"comment":"The notation 'lambda_j(i) != lambda_j(i)' is a typo; it should presumably be 'lambda_j(i) != lambda_i(j)'.","section":"Section II.A, first paragraph"},{"comment":"The text says 'average number of nodes containing truthful information', but the quantity P(G) defined in Eq. (9) is a proportion, not a number; please rephrase consistently.","section":"Abstract and Theorems 3-4"},{"comment":"The notation p^{Theta(log n)} and p^{Theta(sqrt n)} should specify whether the constants in Theta are uniform in n and over the range of p; this matters when p varies with n.","section":"Section IV, Observation 1 and Theorem 4"},{"comment":"Reference [7] is missing the colon in the arXiv identifier and would benefit from a year; the arXiv ids in [7] and [8] should be formatted consistently.","section":"References"}],"recommendation":"reject","confidential_remarks":"The core idea of connecting information quality to first-passage percolation hopcounts is appealing, and the paper is clearly written in places. However, Theorem 1 is false under the stated model because newer packets arriving via non-geodesic routes can overwrite the first-arriving packet. This is not a local gap: the subsequent scaling laws are direct consequences of the false identity. The authors would need to either reformulate the model to remove the overwriting mechanism or develop a last-passage/hopcount analysis for the actually stored packet, which is a substantial revision. I therefore recommend rejection of the current version, while encouraging a resubmission if the central theorem can be repaired."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Core idea: quality as a Markov chain run for the hopcount of the first-passage path. That's a nice way to unify AoI and misinformation, and the two-state specialization gives clean scaling predictions. The paper correctly identifies the literature gap and builds on [8] in a natural way.\n\nWhat it does well: the framework is elegant. Observation 1 is correct, and the qualitative conclusion that denser networks with fresher age degrade slower is plausible and matches [9]'s simulations. The ring analysis, despite an error, is a reasonable attempt at a hopcount bound.\n\nWhere it falls down: Theorem 1's proof has a load-bearing gap. The coupling tracks a single packet along the minimizing path and asserts it 'will survive.' But the source emits a stream of versions at finite λe. A later version, generated ε later, can follow a path with strictly more hops and arrive before the earlier packet's path is finished; because nodes always accept the newer packet, it overwrites the earlier one and becomes the stored packet. Concretely, paths S-A-i (2 hops, delay 2) and S-B-C-i (3 hops, delay 3): version 1 at t=0 arrives at 2; version 2 at t=ε arrives at 3+ε. At t=3+ε node i stores version 2, so Si(t)=M0(3) with positive probability while H(i,n0)=2. The event has positive probability under exponential clocks. So Theorem 1 is false as stated for finite λe. The identity might hold in an infinite-source-rate limit, but the paper doesn't state that assumption. The stress-test note is correct, and it kills the support for Theorems 3 and 4.\n\nThere is also a concrete algebraic error in Lemma 1: (13)-(15) claims P[Exp(1)<Exp(i/n)] = (n-i)/(n+1), but the correct value is n/(n+i). The Θ(√n) may survive a fix, but the bound as written is wrong.\n\nTheorem 3's adaptation from [11] is omitted, and the edge-weight inhomogeneity around the source means 'verbatim' is not obvious.\n\nBottom line: the core idea is worth a serious look, but the main theorem is not established. The k-state generalization and the scaling laws are contingent on a coupling that the proof only sketches. This deserves a careful referee, but not acceptance.\n\nRecommendation: send to peer review with a clear request to fix the coupling (or state λe=∞) and correct the ring lemma.","headline":"The paper's core idea is attractive, but the main theorem has a real coupling gap that likely breaks the hopcount identity, and the ring lemma has a concrete algebraic error.","tokens_in":8446,"tokens_out":14803,"would_cite":false,"duration_ms":153568,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60K35","68M14","94A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A node's stored gossip quality equals the degradation chain applied to the fastest path's hop count.","keywords":["age of information","gossip networks","information degradation","misinformation spread","first-passage percolation","hopcount","Markov chain","truthfulness"],"falsifier":"Simulate the continuous-time gossip process on a small graph, such as a source plus three nodes arranged so that a direct edge and a two-hop path have comparable first-passage times, with explicit rates and a two-state true/false chain; compare the empirical P[Si(t)=T] at each node to $p^{{H(i,n0)}}$. If any positive-probability overwrite along the minimizing path changes the number of Markov transitions the winning packet undergoes, the observed distribution will diverge from the Theorem 1 prediction.","tokens_in":7364,"feed_emoji":"📉","tokens_out":4882,"duration_ms":50368,"temperature":0.7,"pith_summary":"This paper asks how accurate information stays when users gossip: a source sends timestamped updates, nodes forward the newest packet they hold, and each forwarding hop degrades the packet by a fixed Markov chain. The central result is an exact identity: at any time t and node i, the stored quality equals the degradation chain run for exactly the number of hops in the minimum-passage path from the source to i, or is unset if no packet has arrived. A corollary is that in a fully connected network the fraction of nodes holding truthful information is $p^{{Θ(log n)}}$, while on a ring it is $p^{{Θ(√n)}}$, so denser networks preserve truth exponentially longer. This matters because it connects information quality directly to age-of-information scaling and first-passage percolation, turning a packet-quality problem into a hop-count problem.","feed_headline":"Gossip truth decays along the fastest path's hop count","feed_subtitle":"Proven: true-node fraction is p^{Θ(log n)} in cliques, p^{Θ(√n)} on rings — quality follows age.","key_machinery":"The load-bearing object is the reversed auxiliary graph G′: take the gossip graph, reverse every edge, and weight each edge by an independent exponential random variable with the same rate as the gossip update on that edge. The first-passage time T(i,n0) in G′ reproduces the age process, and the number H(i,n0) of edges on the minimizing path is argued to be the exact number of times the degradation Markov chain is applied to the stored packet. All later scaling laws come from bounding this hopcount in the complete graph and the ring.","core_discovery":"The paper establishes Theorem 1: for a gossip network with source n0, if T(i,n0) is the first-passage time in the reversed weighted auxiliary graph and H(i,n0) is the number of edges on the minimizing path, then Si(t) = -1 when T(i,n0) > t and Si(t) = M0(H(i,n0)) otherwise. In other words, a node's information quality is exactly the degradation Markov chain evaluated at the hop count of the fastest path. The proof couples the reversed first-passage process to the age process from earlier work and argues that the packet that wins the race survives without being overwritten. Specializing to a two-state true/false chain, the paper derives P(Kn) = $p^{{Θ(log n)}}$ and P(Cn) = $p^{{Θ(√n)}}$, and conjectures that all gossip networks have hopcount and first-passage time scaling at the same rate, so the networks with the best age of information also spread misinformation the slowest.","pith_inferences":["The paper leaves implicit a testable consequence: in any graph where the hopcount of the first-passage path has a known scaling, the truthful fraction should scale as p raised to that hopcount; for grids this would predict a p^{Θ(n^{1/3})} law if the conjecture holds.","Comparing the paper's 'timeliness prevails' model with the earlier 'truth prevails' model under the same first-passage coupling on K_n or C_n would isolate the effect of stale-packet recovery, which the paper identifies as the likely reason earlier simulations showed more truthful nodes.","If the minimizing-path survival assumption fails under heavy traffic, the true quality distribution could depend on overwrite counts rather than hopcount alone; a small network with two near-equal-speed paths would separate those predictions."],"forward_implications":["If Theorem 1 holds, quality analysis reduces to hopcount analysis: to know what any node stores, compute the fastest-path hop count and run the degradation chain that many steps.","In the fully connected graph, the long-run fraction of truthful nodes is p^{Θ(log n)}; with fixed p below 1 this decays as a power of n.","On the ring, the long-run fraction of truthful nodes is p^{Θ(√n)}, which decays exponentially in √n and is much worse than the clique's polynomial decay.","The source rate and per-edge rates drop out of the quality law except through the first-passage time and hopcount, so the results extend to arbitrary λ after rescaling time.","The paper's conjecture that hopcount and first-passage time scale together in every gossip network implies that networks with the best age-of-information scaling also retain truthful information the longest."],"supporting_citations":[{"why":"Supplies the first-passage percolation characterization of the age process that Theorem 1 extends from age to hopcount quality.","marker":"[8]"},{"why":"Provides the Θ(log n) expected hopcount on the complete graph that yields P(Kn) = p^{Θ(log n)}.","marker":"[11]"},{"why":"Inspires the ring-network hopcount bound through clustered-gossip age techniques used in Lemma 1.","marker":"[5]"},{"why":"Provides grid age-of-information techniques that inform the ring hopcount computation and the conjecture about matching scaling.","marker":"[6]"},{"why":"Supplies the misinformation-spread motivation and the numerical baseline whose simulation trends the paper's results match.","marker":"[9]"},{"why":"Establishes the logarithmic age-of-information scaling in complete gossip networks that the clique result builds on.","marker":"[3]"}],"fun_headline_variants":["Gossip truth decays with every hop, not every second","In gossip networks, misinformation spread tracks age of information","Cliques keep gossip more truthful than rings, show mathematicians","The freshest gossip is also the most truthful gossip"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that the packet which eventually reaches a node travels the exact minimizing path without ever being overwritten by a fresher packet, so the number of Markov-chain transitions equals the hop count; in a continuous gossip stream this survival is asserted via a coupling rather than fully proved.","fun_headline_variants_meta":{"raw":{"variants":["Gossip truth decays with every hop, not every second","In gossip networks, misinformation spread tracks age of information","Cliques keep gossip more truthful than rings, show mathematicians","The freshest gossip is also the most truthful gossip"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000845,"raw_usage":{"total_tokens":3638,"prompt_tokens":867,"completion_tokens":2771,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":483,"completion_tokens_details":{"reasoning_tokens":2714}},"tokens_in":483,"tokens_out":2771,"duration_ms":30426,"temperature":1.0,"reasoning_tokens":2714,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T16:27:55.049073+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the continuous-time gossip process on a small graph, such as a source plus three nodes arranged so that a direct edge and a two-hop path have comparable first-passage times, with explicit rates and a two-state true/false chain; compare the empirical P[Si(t)=T] at each node to $p^{{H(i,n0)}}$. If any positive-probability overwrite along the minimizing path changes the number of Markov transitions the winning packet undergoes, the observed distribution will diverge from the Theorem 1 prediction.","supporting_citations":[{"cited_title":"Age of gossip from connective properties via first passage percolation","cited_arxiv_id":"2409.12710","evidence_quote":"Supplies the first-passage percolation characterization of the age process that Theorem 1 extends from age to hopcount quality."},{"cited_title":"Bhamidi, R","cited_arxiv_id":null,"evidence_quote":"Provides the Θ(log n) expected hopcount on the complete graph that yields P(Kn) = p^{Θ(log n)}."},{"cited_title":"Buyukates, M","cited_arxiv_id":null,"evidence_quote":"Inspires the ring-network hopcount bound through clustered-gossip age techniques used in Lemma 1."},{"cited_title":"Srivastava and S","cited_arxiv_id":null,"evidence_quote":"Provides grid age-of-information techniques that inform the ring hopcount computation and the conjecture about matching scaling."},{"cited_title":"Kaswan and S","cited_arxiv_id":null,"evidence_quote":"Supplies the misinformation-spread motivation and the numerical baseline whose simulation trends the paper's results match."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the logarithmic age-of-information scaling in complete gossip networks that the clique result builds on."}],"review_version":1}