Age of Gossip in Ring Networks With Non-Poisson Updates
2026-05-06 • Information Theory
Information TheoryNetworking and Internet ArchitectureSocial and Information Networks
AI summaryⓘ
The authors study how fresh information spreads through a ring-shaped network of nodes that share updates in a push-based gossip manner. Each connection between nodes gets updates independently but not identical in timing, coming from renewal processes. They focus on measuring the 'version age of information,' which tells how outdated the info at each node is. Using a new sample-path backtracking method, they find that the age grows roughly with the square root of the number of nodes after a node gets its first update. This extends previous work that assumed identical timing for all edges.
Version age of informationGossip protocolRenewal processPoisson processRing networkStochastic hybrid systemsFirst passage percolationSample-path backtrackingInformation freshnessStochastic equivalence
Authors
Arunabh Srivastava, Sennur Ulukus
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.