{"id":"fa562e6c-050a-4f20-891f-933a0578b77b","arxiv_id":"2504.18504","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Fast topology switching in a two-state gossip network makes the average version age scale like the better static topology, and slow switching like the worse one, for all but o(n) atypical nodes.","lead":"This paper analyzes how often a source's updates stay fresh in a network of gossip nodes whose connection pattern switches between two topologies over time. It shows that fast switching inherits the age of the better topology, and introduces a typical set of nodes to handle nodes that lag far behind.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The w.h.p. O(f(n)) per-node bound used in both theorems rests on a false deterministic truncation of the first-passage time; as written, neither main scaling is fully supported.","rationale":"The reader's weakest assumption is the same one I land on: Lemma 1's proof uses a false equality. I agree that this is the most load-bearing gap. The paper's qualitative conclusions are plausible and the framework is reasonable, but the proof of the w.h.p. bound is essential to both Theorem 1 and Theorem 2. I noticed an additional issue in the slow-switching proof: the waiting time B for direct source-to-node transmissions is not the first-passage time from the cited [22] result, so the stated convergence argument is not valid as written. That issue reinforces the conditional verdict rather than changing it, because the underlying claims may still be true with a repaired proof. I am not moving the verdict: the paper should be accepted only if these proof gaps are fixed or replaced with a correct tail/coupling argument. The proposed concrete test is to re-derive Lemma 1 without the forbidden equality and to identify the needed tail estimate; if the estimate holds for the example families, the qualitative results survive.","tokens_in":9273,"tokens_out":25745,"duration_ms":293250,"concrete_test":"Re-derive Lemma 1 directly from the [22] representation X(t)=d min(t,T(1,s)) without using P(min(T,t)=T)=1. The re-derivation must state and prove a tail bound of the form P(T(1,s)>C f(n))=o(1) for a fixed C. Apply the same check to the two running-example graph families, the complete graph and the ring: compute or bound the first-passage-time tail, and verify the w.h.p. O(f(n)) bound. If no such tail bound can be established, replace the direct-source-to-all waiting time B in the proof of Theorem 2 with the true first-passage time T(1,s) and confirm that h(n)=Ω(n log n) dominates the coupling time to the stationary age law.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Both Theorem 1 and Theorem 2 need the following: if a node's stationary version-age mean is Θ(f(n)), then its version age is O(f(n)) with high probability. Lemma 1 is the formal vehicle, and its proof is not valid. It uses the representation X(t)=d min(t,T(1,s)) from [22] and asserts that one can choose a deterministic t0 so that for all t>t0, P(min(T(1,s),t)=T(1,s))=1. This equality is false for any a.s.-finite but unbounded T: for every finite t, P(T(1,s)>t)>0, so the truncated variable differs from T on a positive-probability event. The subsequent contradiction argument about tail mass above O(f(n)) therefore does not follow from the cited representation. The gap is load-bearing: Theorem 1's upper bound uses Lemma 1 to control a single node in the modified G1/disconnected process, and Theorem 2's slow-switching O(f2(n)) bound says its proof is 'along similar lines as Lemma 1.' The alternative route offered in the proof of Theorem 2 does not repair the gap: it defines B as the first time the source has sent an update directly to every node, with E[B]=nH(n), and claims that after B the version-age distribution is the first-passage distribution of [22]. That direct-reception time is not the first-passage time T(1,s); in a complete graph the former is Θ(n log n) and the latter is Θ(log n), so the argument as written cannot justify convergence to stationarity on the h(n) timescale.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a source that generates updates and shares them with n gossiping nodes, where the network topology switches between two static topologies according to a two-state continuous-time Markov chain with holding time Θ(h(n)). The main claims are: (i) if the two static topologies have long-term average version ages Θ(f1(n)) and Θ(f2(n)) with f1(n)=o(f2(n)) and h(n)=O(f1(n)), then the time-varying network's long-term average version age is Θ(f1(n)); (ii) a ``typical set'' of nodes with individual long-term average version age O(f(n)) contains all but o(n) nodes; and (iii) if h(n)=Ω(n log n), the long-term average version age of the typical set is Θ(f2(n)). The results are derived using a per-node high-probability bound (Lemma 1), a lemma on CTMC holding times (Lemma 2), a count of source updates (Lemma 3), and a typical-set cardinality lemma (Lemma 4).","tokens_in":9632,"tokens_out":8046,"duration_ms":77044,"significance":"If the main theorems were correct, the paper would provide a clean scaling rule for dynamic gossip networks: fast switching inherits the faster topology's freshness, slow switching inherits the slower topology's typical-set freshness, and atypical nodes are vanishingly few. The introduction of the typical set is a useful conceptual contribution that addresses a real limitation of average-age analyses in non-vertex-transitive networks. The paper is clearly written and builds on appropriate prior work, including the authors' own published results [22,23]. However, the correctness of the main scaling results is not established because several load-bearing proof steps are invalid as written: the truncation argument in Lemma 1 is false for unbounded first-passage times, and the slow-switching proof in Theorem 2(2) confuses direct source-to-every-node reception with convergence to the first-passage distribution. These gaps affect both main theorems.","major_comments":[{"comment":"The step 'choose t0 = t0(n) so that for all t > t0, P(min(T(1,s), t) = T(1,s)) = 1' is false whenever T(1,s) is almost surely finite but unbounded, which is the case for first-passage times in this gossip model: for every finite t, P(T(1,s) > t) > 0. Therefore the truncated random variable min(T(1,s), t) is not equal to T(1,s) on a positive-probability event for any finite t, and the argument that the distribution stabilizes after t0, together with the contradiction about tail mass above O(f(n)), does not follow from the representation X(t) =d min(t, T(1,s)) taken from [22]. Since this lemma supplies the w.h.p. O(f(n)) per-node bound used in the upper bound of Theorem 1 and is invoked 'along similar lines' in Theorem 2(2), the proof gap is load-bearing for both main scaling results.","section":"Appendix, Proof of Lemma 1"},{"comment":"The proof of Theorem 2(2) does not justify convergence to the first-passage distribution. The random variable B = sup_i B_i is the first time the source has sent an update directly to every node, not the first-passage time T(1,s) from the source to a node. These are different objects: in a complete graph E[B] = Θ(n log n) while the first-passage time to a fixed node is Θ(log n). The bound in Eq. (4), P(|B - E[B]| > n log n) ≤ 1/(log n)^2, only shows that direct reception by all nodes occurs within Θ(n log n) w.h.p.; it does not imply that the version-age distribution has converged to the stationary distribution of the static network, nor that the mean version age in an interval of length h(n) is Θ(f2(n)). The additional claim that the expectation is O(f2(n)) w.h.p. 'along similar lines as Lemma 1' inherits the invalid truncation argument of Lemma 1. Thus the Θ(f2(n)) lower bound for the typical set under slow switching is not established.","section":"Theorem 2(2) proof"},{"comment":"The proof of Lemma 4 only rules out a constant fraction of atypical nodes. The proof assumes the atypical set has kn nodes for a constant 0<k<1 and derives a contradiction with v_{G_n} = Θ(f(n)). To conclude that the complement of the typical set has o(n) nodes, one must rule out any non-vanishing density, such as ε n for arbitrary ε>0 or n/log n. The argument as written does not exclude these cases, so the statement 'its complement contains o(n) nodes' is not proven. This affects Corollary 1 and the interpretation that the typical set contains all but a vanishingly small fraction of nodes.","section":"Section IV, Lemma 4"},{"comment":"The proof of Theorem 1 contains an inconsistent scaling in the definition of the good event. After fixing the total time in G1 to be β g(n) (where g(n) is the claimed age scaling of node 1), the event A is defined as {f_k ≤ α log n, N_0[0,f_k] ≤ α log n}. Here f_k is the absolute time at which the k-th G1 interval ends; with h(n)=O(f1(n)) the process may switch many times, so f_k need not be Θ(g(n)), and neither inequality follows from Lemma 3. The proof also asserts without derivation that during the disconnected intervals the age 'scales as O(h(n))'; this requires a bound on the age at the switching instants, which the static-network Lemma 1 does not provide. Since this is the mechanism for the O(f1(n)) upper bound, the fast-switching result is not established as written.","section":"Proof of Theorem 1"}],"minor_comments":[{"comment":"The definition of Θ(n) after Eq. (1) states 'c1 ≤ lim_{n→∞} f(n)/g(n) ≤ c2', which requires the limit to exist; the standard definition should use liminf and limsup or state that the ratio is bounded between positive constants for all large n.","section":"Section II, notation"},{"comment":"In the proof of Theorem 2(2), the displayed inequality has 'Var[X]' but should be 'Var[B]'.","section":"Eq. (4)"},{"comment":"Notation for the source update count is inconsistent: the system model uses N0(t), Lemma 3 uses N0([0,T]), and the proof of Theorem 1 uses N0[0,f_k]; please unify.","section":"Throughout"},{"comment":"The constants η, χ, ρ, ξ are introduced as 'η∈R' and 'χ∈R' without specifying the required positivity or size conditions; the inequalities in Eqs. (6)–(14) need these conditions to be meaningful.","section":"Proof of Lemma 2"}],"recommendation":"major_revision","confidential_remarks":"The paper's main results are plausible and the typical-set formulation is a useful contribution, but the current proofs of Lemma 1 and Theorem 2(2) contain invalid steps. Given that the central scaling theorems rest on these steps, I recommend major revision. The authors will need to replace the truncation argument in Lemma 1 with a valid tail-bound or coupling argument and re-derive the slow-switching result using a proper stationarity or regeneration argument. If the claims cannot be repaired, the paper would require substantial restructuring."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper asks a good question — what happens to version age when a gossip network alternates between two arbitrary topologies — and the answer it gives (fast switching inherits the better topology, very slow switching leaves the typical set at the worse one) is probably right. The typical set definition is a legitimate addition, and the observation that a vanishing fraction of nodes can dominate the average is correct and worth having. Credit where it is due: the problem is well posed, the scaling setup is clean, and there are no fitted parameters. The paper builds on the authors' own prior work [22,23], but those are independent published results, so the citation pattern looks honest.\n\nThe soft spots are in the proofs, and they hit load-bearing parts. Lemma 1's proof asserts that for some finite t0, P(min(T,t)=T)=1 for all t>t0. For an a.s. finite but unbounded first-passage time T that equality is false — for every finite t there is positive probability T>t. The contradiction argument about tail mass at ω(f(n)) therefore does not follow. That matters because Theorem 1's upper bound uses Lemma 1 directly, and Theorem 2's slow-switching bound says it follows 'along similar lines.' The alternative route in Theorem 2 uses B, the first time the source has sent an update directly to every node, and treats that as the first-passage time. It isn't: in a complete graph B is Θ(n log n) while the gossip first-passage time is Θ(log n). So the stationarity argument on the h(n) timescale is not justified as written. I would also flag Lemma 4: the proof assumes the non-typical set has size kn for a constant k, which is close to what the lemma is supposed to prove; the intended contradiction can probably be recovered by a subsequence argument, but it is not written. And there is a smaller internal inconsistency in Theorem 1's proof, where bounds are written as α log n while the theorem is about general f1(n).\n\nNone of this feels fatal. The qualitative claims are sensible, and I would expect the gaps to be patchable with a proper concentration argument or a corrected appeal to [22]. But as it stands, the two main scaling theorems are not fully supported.\n\nThis is a paper for people working on age of information over gossip, especially dynamic topologies. It deserves a serious referee, not a desk reject. My recommendation: send it out, with a note to the authors that Lemma 1 and the B-step in Theorem 2 need to be fixed before acceptance.","headline":"Worth engaging — the typical-set idea is new and the qualitative story is plausible — but as written the main theorems lean on a faulty lemma and should not be accepted without a serious revision.","tokens_in":10124,"tokens_out":7013,"would_cite":true,"duration_ms":70432,"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 gossip network that switches between two topologies inherits the fresher topology's age when switching is fast, and the staler topology's age when switching is very slow.","keywords":["version age of information","gossip networks","time-varying topologies","continuous-time Markov chain","typical set","fast switching","slow switching","first-passage percolation"],"falsifier":"For a static ring topology, compute $P(T>t_0)$ where $T$ is the first time the source's version reaches a fixed node and $t_0$ grows with $n$. If for every $t_0(n)=o(n\\log n)$ this probability is positive and not $o(1)$, the deterministic cutoff used in Lemma 1 cannot hold. Alternatively, simulate the two-topology system with $h(n)=\\Theta(\\log n)$ and check whether the average version age tracks $\\Theta(\\log n)$ rather than $\\Theta(\\sqrt{n})$.","tokens_in":9106,"feed_emoji":"🔄","tokens_out":6672,"duration_ms":68130,"temperature":0.7,"pith_summary":"This paper asks how information freshness behaves when a gossip network does not stay in one topology but switches between two fixed topologies according to a continuous-time Markov chain. It claims that when the switching is fast, the time-varying network's long-term average version age matches the better (smaller) of the two static topologies' ages, and when switching is very slow, the typical nodes end up with the worse topology's age. To make this precise it introduces a 'typical set' of nodes whose ages scale like the network average, excluding at most $o(n)$ atypical nodes. A sympathetic reader should care because real networks change their connectivity over time, and prior freshness results mostly considered static topologies.","feed_headline":"Fast switching keeps gossip networks at the fresher topology's age","feed_subtitle":"Under slow switching, the network ages like its worse topology; a tiny atypical set can distort averages.","key_machinery":"The central object is the version age $X_i(t)=N_0(t)-N_i(t)$, the difference between the source's version counter and node $i$'s counter, with the CTMC holding time $h(n)$ controlling how long each topology persists. The proof machinery is a set of lemmas: Lemma 1 converts a $\\Theta(f(n))$ mean age into a high-probability per-node $O(f(n))$ bound, Lemma 2 guarantees the CTMC spends a constant fraction of wall-clock time in each state, and Lemma 3 matches the source's update count to elapsed time. The deepest input is the representation from [22] of the stationary age at a node as $\\min(t, T(1,s))$, the minimum of the elapsed time and the first-passage time from the source to that node; this representation drives both the fast-switching upper bound and the slow-switching lower bound.","core_discovery":"The paper's central claim is a dichotomy. For two topology sequences with long-term average version ages $\\Theta(f_1(n))$ and $\\Theta(f_2(n))$, where $f_1(n)=o(f_2(n))$, a two-state continuous-time Markov chain with holding time $h(n)$ yields a time-varying network whose long-term average version age is $\\Theta(f_1(n))$ when $h(n)=O(f_1(n))$ (Theorem 1). For the typical set of nodes, the same fast-switching result holds, and if $h(n)=\\Omega(n\\log n)$ the typical-set version age becomes $\\Theta(f_2(n))$ (Theorem 2). This says that dynamic switching inherits the faster topology's freshness exactly when switching is fast, and the slower topology's freshness once switching becomes very slow, with a vanishing fraction of atypical nodes allowed to behave differently.","pith_inferences":["A natural conjecture the paper leaves open is a monotone interpolation: as $h(n)$ grows from $f_1(n)$ toward $n\\log n$, the typical-set age should rise from $\\Theta(f_1(n))$ to $\\Theta(f_2(n))$; this could be tested on the fully-connected/ring example for intermediate holding times.","The typical-set concept transfers to non-vertex-transitive topologies and to other freshness metrics; the averaging trap shown in the paper's combined fully-connected/line example should appear whenever a small subnetwork has age $\\omega(f(n))$.","The deterministic cutoff step in Lemma 1 is the most delicate point: if first-passage times have unbounded tails, the high-probability bounds would need a distribution-tail argument in place of the written equality, though the qualitative dichotomy could still hold."],"forward_implications":["If Theorem 1 holds, network designers can treat the faster topology's age as the freshness bottleneck under fast switching, since the slower topology contributes only $O(h(n))$ additional age while it is active.","If Theorem 2 holds, very slow switching forces typical nodes back to the worse topology's age, so frequent switching is necessary to preserve freshness gains.","The typical-set result shows that $\\Omega(n)$ nodes scale like the network average and only $o(n)$ nodes can be outliers, which limits but does not eliminate the risk of a few badly aged nodes.","For intermediate holding times with $f_1(n) \\ll h(n) \\ll n\\log n$, the paper gives a universal $O(f_2(n))$ upper bound, leaving the exact scaling open."],"supporting_citations":[{"why":"Supplies the SHS recursive equations and the static-network bounds $\\log n \\le f(n) \\le n$ used to frame Theorem 1.","marker":"[12]"},{"why":"Provides the stationary version-age representation as $\\min(t, T(1,s))$ that Lemma 1 and the slow-switching lower bound rely on.","marker":"[22]"},{"why":"Gives the restricted dynamic-topology result for fully-connected networks whose proof technique Theorem 1 generalizes.","marker":"[23]"},{"why":"Introduces the spatial mean-field analysis of gossip age that motivates the version-age model used throughout.","marker":"[15]"},{"why":"Supplies random and bipartite graph examples used as natural graph sequences with known age scalings.","marker":"[20]"},{"why":"Provides generalized-ring graph sequences with easy parametrization used to illustrate typical sets and age scalings.","marker":"[24]"}],"fun_headline_variants":["Fast switching keeps gossip age at the fresher topology's level","Gossip age: rapid switching adopts the fresher topology's age","Typical gossip nodes see fresh age when switching is quick","Gossip freshness: switch speed picks fast or slow topology's age"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The scaling results assume that after a deterministic waiting time, each node's version age is almost surely equal to the first-passage time from the source, with no remaining chance of a longer wait; if that equality is false, the fast- and slow-switching scalings do not follow from the given proofs.","fun_headline_variants_meta":{"raw":{"variants":["Fast switching keeps gossip age at the fresher topology's level","Gossip age: rapid switching adopts the fresher topology's age","Typical gossip nodes see fresh age when switching is quick","Gossip freshness: switch speed picks fast or slow topology's age"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001632,"raw_usage":{"total_tokens":6491,"prompt_tokens":951,"completion_tokens":5540,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":567,"completion_tokens_details":{"reasoning_tokens":5466}},"tokens_in":567,"tokens_out":5540,"duration_ms":47746,"temperature":1.0,"reasoning_tokens":5466,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:15:14.490641+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a static ring topology, compute $P(T>t_0)$ where $T$ is the first time the source's version reaches a fixed node and $t_0$ grows with $n$. If for every $t_0(n)=o(n\\log n)$ this probability is positive and not $o(1)$, the deterministic cutoff used in Lemma 1 cannot hold. Alternatively, simulate the two-topology system with $h(n)=\\Theta(\\log n)$ and check whether the average version age tracks $\\Theta(\\log n)$ rather than $\\Theta(\\sqrt{n})$.","supporting_citations":[{"cited_title":"Srivastava, T","cited_arxiv_id":null,"evidence_quote":"Gives the restricted dynamic-topology result for fully-connected networks whose proof technique Theorem 1 generalizes."},{"cited_title":"Chaintreau, J","cited_arxiv_id":null,"evidence_quote":"Introduces the spatial mean-field analysis of gossip age that motivates the version-age model used throughout."}],"review_version":1}