arxiv: 2605.05152 · v1 · submitted 2026-05-06 · 💻 cs.IT · cs.NI· cs.SI· eess.SP· math.IT

Recognition: unknown

Age of Gossip in Ring Networks With Non-Poisson Updates

Arunabh Srivastava , Sennur Ulukus

Authors on Pith no claims yet

Pith reviewed 2026-05-08 16:03 UTC · model grok-4.3

classification 💻 cs.IT cs.NIcs.SIeess.SPmath.IT

keywords version age of informationgossip networksring networksrenewal processesstochastic equivalenceage of gossipinformation freshness

0 comments

The pith

In a ring of n nodes using independent renewal updates on each link, the version age at any node is stochastically equivalent to sqrt(n) after the node receives its first update from the source.

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

The paper studies a ring network where a source sends updates through a Poisson process and nodes exchange versions using push gossip over independent renewal processes that need only finite mean and variance. It replaces earlier Poisson-only or identical-edge assumptions with a sample-path backtracking method that traces how each version reaches a given node. The central finding is that the version age process at every node matches sqrt(n) in distribution once the first update arrives. This scaling is shown to hold for both one-way and two-way rings. The result matters because it shows that local gossip can keep information reasonably fresh in large rings without requiring synchronized clocks or identical link timings.

Core claim

The version age of information of any node in the network is stochastically equivalent to √n at any time instant after the node has received its first update from the source. This equivalence is established for both uni-directional and bi-directional ring networks in which every edge follows an independent renewal process with finite mean and variance, while the source disseminates updates according to a Poisson process.

What carries the argument

Sample-path backtracking that follows the most recent version's arrival path backwards from the target node through the ring until it reaches the source.

If this is right

The sqrt(n) stochastic scaling holds for both uni-directional and bi-directional rings.
The scaling is insensitive to the precise distributions on each edge provided the processes remain independent with finite mean and variance.
The same order is obtained whether the source uses a Poisson process or another renewal process for initial dissemination.
Once a node receives its first update, its version age stays stochastically of order sqrt(n) at all later times.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same backtracking idea could be applied to other sparse regular graphs such as grids or tori to test whether sqrt(n) scaling persists.
Numerical checks for moderate n would reveal how closely the finite-n age distribution approaches its sqrt(n) limit.
Relaxing the finite-variance condition on the renewal processes might produce a different scaling exponent.

Load-bearing premise

The backtracking procedure correctly reproduces the version-age process for arbitrary independent renewal processes on the edges as long as each has finite mean and variance.

What would settle it

A large-n simulation or exact calculation for a specific non-Poisson renewal distribution on the edges in which the version age at a typical node grows faster or slower than order sqrt(n) after the first update arrives.

Figures

Figures reproduced from arXiv: 2605.05152 by Arunabh Srivastava, Sennur Ulukus.

**Figure 1.** Figure 1: An illustration of the uni-directional ring network (top), and the bi view at source ↗

read the original abstract

We consider a network consisting of $n$ nodes connected in a ring formation and a source that generates updates according to a renewal process and disseminates them to the ring network according to a Poisson process. The nodes in the network gossip with each other according to a push-based gossiping protocol, and disseminate version updates. Gossip between two neighbors happens at the arrivals of renewal processes with finite mean and variance. All renewal processes and Poisson processes in the network are independent but not identically distributed. We consider both uni-directional ring networks and bi-directional ring networks. We use version age of information to quantify the freshness of information at each node. Prior work has used the stochastic hybrid systems (SHS) approach or a first passage percolation (FPP) approach to analyze ring networks with edges following identical Poisson processes. In this work, we use a sample-path backtracking approach to characterize the probabilistic scaling of the version age of information of an arbitrary node in the gossip network, where each edge follows an independent but not identically distributed renewal process. We show that the version age of information of any node in the network is stochastically equivalent to $\sqrt{n}$ at any time instant after the node has received its first update from the source.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper extends the sqrt(n) version age scaling to non-identical renewal gossip on rings via sample-path backtracking, but the abstract leaves the handling of residual lifetimes and exact equivalence conditions unclear.

read the letter

The main point is that this work generalizes the sqrt(n) scaling for version age in ring networks from Poisson-only edges to independent but non-identical renewals with finite mean and variance. The authors apply a sample-path backtracking argument to both uni-directional and bi-directional rings, where the source uses Poisson updates and nodes gossip via push-based renewals. They claim that after any node receives its first source update, its version age is stochastically equivalent to sqrt(n) at any later time.

Referee Report

1 major / 2 minor

Summary. The manuscript analyzes version age of information in uni- and bi-directional ring networks of n nodes. A source generates updates via a renewal process and injects them into the ring via Poisson arrivals; neighboring nodes exchange version updates via independent but non-identical renewal processes possessing only finite mean and variance. Prior Poisson-only analyses relied on stochastic hybrid systems or first-passage percolation. The authors introduce a sample-path backtracking construction and conclude that, after any node receives its first source update, its version age is stochastically equivalent to √n.

Significance. If the claimed stochastic equivalence holds, the result establishes that the √n scaling of version age is insensitive to the precise inter-update distributions provided only finite moments exist, thereby extending the reach of age-of-information theory beyond memoryless models. The sample-path backtracking technique itself constitutes a methodological contribution that may apply to other non-Markovian gossip settings.

major comments (1)

[Proof of the main theorem] Proof of the main theorem (the backtracking argument): the claim of exact stochastic equivalence to √n for arbitrary independent non-identical renewals with only finite mean and variance requires an explicit demonstration that residual lifetimes and the resulting path-dependent correlations are neutralized exactly by the backtracking construction. The finite-moment hypothesis alone does not automatically guarantee this cancellation; additional regularity (non-lattice condition, uniform integrability of the renewal functions, or an error-term bound) appears necessary yet is not stated.

minor comments (2)

Notation for the version-age random variable and the precise definition of 'stochastically equivalent to √n' should be introduced earlier and used consistently throughout the backtracking derivation.
The abstract and introduction would benefit from a single sentence listing the exact technical conditions (e.g., non-lattice, finite variance) under which the equivalence is proved.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback on our manuscript. The major comment on the proof is addressed below with clarifications and a commitment to revision.

read point-by-point responses

Referee: Proof of the main theorem (the backtracking argument): the claim of exact stochastic equivalence to √n for arbitrary independent non-identical renewals with only finite mean and variance requires an explicit demonstration that residual lifetimes and the resulting path-dependent correlations are neutralized exactly by the backtracking construction. The finite-moment hypothesis alone does not automatically guarantee this cancellation; additional regularity (non-lattice condition, uniform integrability of the renewal functions, or an error-term bound) appears necessary yet is not stated.

Authors: We appreciate the referee's observation that the neutralization of residuals and correlations in the backtracking argument merits explicit demonstration. Our sample-path construction backtracks information flow from the target node along all possible gossip paths in the ring, using independence of the renewal processes to equate the version age exactly to the minimum cumulative delay over these paths after the first source update. This min operation, together with the ring topology, directly produces the √n stochastic equivalence without invoking limiting theorems, so that residuals along intersecting paths cancel pathwise and finite mean/variance suffice to control the scaling. We acknowledge that this cancellation step was presented implicitly rather than with a dedicated lemma. To address the concern, we will add an explicit paragraph in the proof section showing the neutralization under the stated assumptions alone (no non-lattice or uniform-integrability conditions are required, as the equivalence is distributional and holds at finite times). The core result is unchanged. revision: yes

Circularity Check

0 steps flagged

No circularity in sample-path backtracking derivation of √n scaling

full rationale

The paper introduces a sample-path backtracking construction to analyze version age under independent non-identical renewal processes on a ring. The claimed stochastic equivalence of version age to √n after first source update is presented as a direct consequence of this construction applied to the network topology and finite-moment assumptions, rather than presupposed by definition, obtained via parameter fitting, or reduced to a prior self-citation chain. No equations or steps in the abstract or described method exhibit self-definition, fitted-input renaming, or load-bearing uniqueness imported from the authors' earlier work; the derivation remains self-contained against the stated renewal-process inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available; no free parameters, invented entities, or non-standard axioms are mentioned. The finite-mean-and-variance condition on renewals is a standard domain assumption from renewal theory.

axioms (1)

domain assumption All renewal processes have finite mean and variance
Stated explicitly for gossip processes between neighbors.

pith-pipeline@v0.9.0 · 5526 in / 1220 out tokens · 40390 ms · 2026-05-08T16:03:24.246351+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

20 extracted references

[1]

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

2019
[2]

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

2020
[3]

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

2012
[4]

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

2019
[5]

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

2021
[6]

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
[7]

Zhong, R

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

2018
[8]

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
[9]

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

2021
[10]

Abolhassani, J

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

2021
[11]

Bastopcu and S

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

2020
[12]

Buyukates, M

B. Buyukates, M. Bastopcu, and S. Ulukus. Age of gossip in networks with community structure. InIEEE SPA WC, September 2021

2021
[13]

Srivastava and S

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

2023
[14]

Kaswan and S

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

2022
[15]

Kaswan, P

P. Kaswan, P. Mitra, A. Srivastava, and S. Ulukus. Age of information in gossip networks: A friendly introduction and literature survey.IEEE Transactions on Communications, 73(8):6200–6220, February 2025

2025
[16]

Srivastava and S

A. Srivastava and S. Ulukus. Age of gossip on a grid. InAllerton Conference, September 2023

2023
[17]

Mitra and S

P. Mitra and S. Ulukus. ASUMAN: Age sense updating multiple access in networks. InAllerton Conference, September 2022

2022
[18]

Srivastava, T

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

2025
[19]

Kaswan and S

P. Kaswan and S. Ulukus. Timeliness in cache-aided networks with non- poisson updating.IEEE Transactions on Communications, 73(8):6068– 6080, August 2025

2025
[20]

G. Lorden. On excess over the boundary.The Annals of Mathematical Statistics, 41(2):520–527, April 1970

1970