Information Freshness in Dynamic Gossip Networks

Arunabh Srivastava; Sennur Ulukus; Thomas Jacob Maranzatto

REVIEW 4 major objections 4 minor 24 references

Information Freshness in Dynamic Gossip Networks

T0 review · 4 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read 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.

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

arxiv 2504.18504 v1 pith:7ZKQMFCZ submitted 2025-04-25 cs.IT cs.NIcs.SIeess.SPmath.IT

Arunabh Srivastava , Thomas Jacob Maranzatto , Sennur Ulukus This is my paper · ORCID

classification cs.ITcs.NIcs.SIeess.SPmath.IT

keywords versionageofinformationgossipnetworkstime-varyingtopologiescontinuous-timeMarkovchaintypicalsetfastswitchingslowfirst-passagepercolation

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

What carries the argument

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.

What would settle it

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

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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.

Desk Editor's Note

read the 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.

The 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).

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

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

Referee Report

4 major / 4 minor

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

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 (4)

[Appendix, Proof of Lemma 1] 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.
[Theorem 2(2) proof] 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 IV, Lemma 4] 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.
[Proof of Theorem 1] 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.

minor comments (4)

[Section II, notation] 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.
[Eq. (4)] In the proof of Theorem 2(2), the displayed inequality has 'Var[X]' but should be 'Var[B]'.
[Throughout] 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.
[Proof of Lemma 2] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the dynamic results are conditional on given scalings and rely on independent static-network theorems, though some proof steps have correctness gaps.

full rationale

The paper contains no fitted parameters and no data-subset predictions: all claims are asymptotic and conditional on the given scalings f1(n), f2(n), and h(n). The main load-bearing external inputs are [22], the static-network result that version age has the distribution of min(t, first-passage time), and [23], the prior fast-switching result for fully connected topologies. Both are prior works by the same research group, but they are not restatements of this paper's dynamic claims: [22] concerns static gossip networks and [23] treats a restricted fully connected case that the present arbitrary-topology argument generalizes rather than assumes. Lemma 1 is derived from the [22] representation, not from Theorem 1 or Theorem 2, so the w.h.p. O(f(n)) bound is not imported as the conclusion being proved. The typical-set definition is new and is not used as evidence for itself; Lemma 4 follows by averaging arguments. The proof issues noted by the reviewer—the choice of a deterministic t0 with P(min(T,t)=T)=1 for an a.s.-finite unbounded first-passage time, and the use of direct source-reception time B instead of the first-passage time in Theorem 2—are mathematical correctness concerns about the proof, not circularity, because even if valid they would not make the derived scaling equal to an input by construction. The central claims retain independent content relative to their inputs, so the circularity burden is low.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces the mathematical definition of a typical set, but no new physical entities, forces, or fitted parameters. All scaling relations are expressed in terms of the given static ages f1(n), f2(n) and the switching scale h(n).

assumptions (5)

standard math The stationary version age distribution at a node equals the distribution of min(t, first passage time from source to node).
Used in Lemma 1 and Theorem 2; cited to [22], a prior result by a co-author, not re-derived here.
domain assumption All nodes communicate with a constant total rate λ, and the source updates at constant rate λe; these rates do not scale with n.
System model in Section II; the asymptotic results are stated under these fixed rates.
domain assumption The CTMC holding time in each topology is Θ(h(n)) with transition rates q12,q21=Θ(1/h(n)), and the CTMC spends a constant fraction of time in each topology.
Assumed in Section II and proven in Lemma 2; both theorems depend on this time-partition.
standard math For any static gossip network the long-term average version age is between Θ(log n) and Θ(n).
Invoked in Section III from bounds in [12].
domain assumption Version age is monotone in the edge set: replacing a topology by a better one cannot increase the age of the switched network.
Used without proof in the lower bound of Theorem 1 when G2 is replaced by G1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Information Freshness in Dynamic Gossip Networks." pith.science (2026). https://pith.science/paper/7ZKQMFCZ

@misc{pith2026250418504,
  author       = {Pith},
  title        = {Pith review of: Information Freshness in Dynamic Gossip Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7ZKQMFCZ}},
  note         = {Machine review of arXiv:2504.18504}
}

abstract

We consider a source that shares updates with a network of $n$ gossiping nodes. The network's topology switches between two arbitrary topologies, with switching governed by a two-state continuous time Markov chain (CTMC) process. Information freshness is well-understood for static networks. This work evaluates the impact of time-varying connections on information freshness. In order to quantify the freshness of information, we use the version age of information metric. If the two networks have static long-term average version ages of $f_1(n)$ and $f_2(n)$ with $f_1(n) \ll f_2(n)$, then the version age of the varying-topologies network is related to $f_1(n)$, $f_2(n)$, and the transition rates in the CTMC. If the transition rates in the CTMC are faster than $f_1(n)$, the average version age of the varying-topologies network is $f_1(n)$. Further, we observe that the behavior of a vanishingly small fraction of nodes can severely impact the long-term average version age of a network in a negative way. This motivates the definition of a typical set of nodes in the network. We evaluate the impact of fast and slow CTMC transition rates on the typical set of nodes.

Figures

Figures reproduced from arXiv: 2504.18504 by the authors.

**Figure 2.** A network formed by combining a fully-connected network with 2 2 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 17 canonical work pages

[22]

T. J. Maranzatto and M. Michelen. Age of gossip from connective prop- erties via first passage percolation. 2024. Available at arXiv:2409.12710

arXiv 2024
[1]

S. R. Pokhrel, J. Ding, J. Park, O. Park, and J. Choi. Towards enabling critical mmtc: A review of urllc within mmtc. IEEE Access, 8:131796– 131813, 2020

work page 2020
[2]

Chettri and R

L. Chettri and R. Bera. A comprehensive survey on internet of things (IoT) toward 5G wireless systems. IEEE Internet of Things Journal , 7(1):16–32, October 2019

work page 2019
[3]

S. N. Swamy and S. R. Kota. An empirical study on system level aspects of internet of things (IoT). IEEE Access , 8:188082–188134, October 2020

work page 2020
[4]

S. K. Kaul, R. D. Yates, and M. Gruteser. Real-time status: How often should one update? In IEEE Infocom, March 2012

work page 2012
[5]

Y . Sun, I. Kadota, R. Talak, and E. Modiano. Age of information: A new metric for information freshness. Synthesis Lectures on Communication Networks, 12(2):1–224, December 2019

work page 2019
[6]

R. D. Yates, Y . Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus. Age of information: An introduction and survey. IEEE Jour. on Selected Areas in Communications , 39(5):1183–1210, May 2021

work page 2021
[7]

R. D. Yates and S. K. Kaul. The age of information: Real-time status updating by multiple sources. IEEE Transactions on Information Theory, 65(3):1807–1827, March 2018

work page 2018

Show all 24 references

[8]

Banerjee, S

S. Banerjee, S. Ulukus, and A. Ephremides. To re-transmit or not to re-transmit for freshness. In IEEE WiOpt, August 2023

2023
[9]

Maatouk, S

A. Maatouk, S. Kriouile, M. Assaad, and A. Ephremides. The age of incorrect information: A new performance metric for status updates. IEEE/ACM Trans. on Networking , 28(5):2215–2228, October 2020

2020
[10]

Zhong, R

J. Zhong, R. D. Yates, and E. Soljanin. Two freshness metrics for local cache refresh. In IEEE ISIT, June 2018

2018
[11]

Cho and H

J. Cho and H. Garcia-Molina. Effective page refresh policies for web crawlers. ACM Trans. on Database Systems , 28(4):390–426, December 2003

2003
[12]

R. D. Yates. The age of gossip in networks. In IEEE ISIT, July 2021

2021
[13]

Abolhassani, J

B. Abolhassani, J. Tadrous, A. Eryilmaz, and E. Yeh. Fresh caching for dynamic content. In IEEE Infocom, May 2021

2021
[14]

Bastopcu and S

M. Bastopcu and S. Ulukus. Who should Google Scholar update more often? In IEEE Infocom, July 2020

2020
[15]

Chaintreau, J

A. Chaintreau, J. Y . Le Boudec, and N. Ristanovic. The age of gossip: spatial mean field regime. ACM SIGMETRICS Performance Evaluation Review, 37(1):109–120, June 2009

2009
[16]

Buyukates, M

B. Buyukates, M. Bastopcu, and S. Ulukus. Version age of information in clustered gossip networks. IEEE Jour. on Selected Areas in Informa- tion Theory, 3(1):85–97, March 2022

2022
[17]

Kaswan and S

P. Kaswan and S. Ulukus. Age of gossip in ring networks in the presence of jamming attacks. In Asilomar Conference, October 2022

2022
[18]

Mitra and S

P. Mitra and S. Ulukus. Timely opportunistic gossiping in dense networks. In IEEE Infocom, May 2023

2023
[19]

Srivastava and S

A. Srivastava and S. Ulukus. Mobility in age-based gossip networks. In Allerton Conference, September 2024

2024
[20]

T. J. Maranzatto. Age of gossip in random and bipartite networks. In IEEE ISIT, July 2024

2024
[21]

Kaswan, P

P. Kaswan, P. Mitra, A. Srivastava, and S. Ulukus. Age of information in gossip networks: A friendly introduction and literature survey. IEEE Trans. on Communications . To appear. Available at arXiv:2312.16163

arXiv
[23]

Srivastava, T

A. Srivastava, T. J. Maranzatto, and S. Ulukus. Age of gossip with time-varying topologies. In IEEE ISIT, June 2025

2025
[24]

Srivastava and S

A. Srivastava and S. Ulukus. Age of gossip on generalized rings. In IEEE MILCOM, October 2023

2023

Pith tools

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

[1] [22]

T. J. Maranzatto and M. Michelen. Age of gossip from connective prop- erties via first passage percolation. 2024. Available at arXiv:2409.12710

arXiv 2024

[2] [1]

S. R. Pokhrel, J. Ding, J. Park, O. Park, and J. Choi. Towards enabling critical mmtc: A review of urllc within mmtc. IEEE Access, 8:131796– 131813, 2020

work page 2020

[3] [2]

Chettri and R

L. Chettri and R. Bera. A comprehensive survey on internet of things (IoT) toward 5G wireless systems. IEEE Internet of Things Journal , 7(1):16–32, October 2019

work page 2019

[4] [3]

S. N. Swamy and S. R. Kota. An empirical study on system level aspects of internet of things (IoT). IEEE Access , 8:188082–188134, October 2020

work page 2020

[5] [4]

S. K. Kaul, R. D. Yates, and M. Gruteser. Real-time status: How often should one update? In IEEE Infocom, March 2012

work page 2012

[6] [5]

Y . Sun, I. Kadota, R. Talak, and E. Modiano. Age of information: A new metric for information freshness. Synthesis Lectures on Communication Networks, 12(2):1–224, December 2019

work page 2019

[7] [6]

R. D. Yates, Y . Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus. Age of information: An introduction and survey. IEEE Jour. on Selected Areas in Communications , 39(5):1183–1210, May 2021

work page 2021

[8] [7]

R. D. Yates and S. K. Kaul. The age of information: Real-time status updating by multiple sources. IEEE Transactions on Information Theory, 65(3):1807–1827, March 2018

work page 2018