Deriving Moments in the Age of Gossip Process from Percolation

Thomas Jacob Maranzatto, Sennur Ulukus · 2025

Read Deriving Moments in the Age of Gossip Process from Percolation by Thomas Jacob Maranzatto, Sennur Ulukus (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-13981.txt.

Introduction

Thomas Jacob Maranzatto and Sennur Ulukus derive age-of-information identities in a 2025 networking paper. In gossip networks, nodes pass updates to random neighbors, and the age of information measures how stale each node's picture of the source is. Exact formulas for the moments of that age process, its averages and spreads, are the field's basic currency.

A recent link between gossip age and first passage percolation, the spread of a fluid through a random medium, lets the authors recover known recursive identities for every moment of the age. Their proofs are shorter than the originals and need only elementary probability, adapting techniques familiar in statistical physics, with noted connections to the Eden growth model. The cleaner derivations should make the identities easier to teach and extend.

Catalog record

CREATORThomas Jacob Maranzatto, Sennur Ulukus
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-13981

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Deriving Moments in the Age of Gossip Process from Percolation Thomas Jacob Maranzatto, Sennur Ulukus Abstract This paper concerns fundamental identities in the study of age of information (AoI) in gossip networks. We recover known recursive identities for arbitrary k k th moments of the age process based on the recent connection between AoI and first passage percolation. Apart from the connection to percolation, our proofs are more concise and can be followed using only elementary facts from probability. Our argument generalizes some techniques known in the statistical physics community, and we remark on connections to the Eden model. † † address: Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 1 Introduction Given a network of interacting users, a fundamental question is to quantify the freshness of their stored data. This paper considers the age of information (AoI) metric over systems of gossiping users, where users send packets to neighbors randomly. The AoI metric was first introduced by Kaul, Yates, and Gruteser [ 1 ] , and we direct the reader to the survey [ 2 ] for background on related metrics over a wide class of communication and queuing models. Our focus is on a gossiping model introduced by Yates [ 3 ] . Here, a directed network of N users G=(\mathcal{N},E) communicate in a decentralized manner by sending packets to their immediate neighbors. Without loss of generality, take \mathcal{N}=[0,\ldots,N] , and distinguish the node 0 (sometimes referred to as node n_{0} ) as the source so only directed edges of the type (0,u) exist, never (u,0) . The source acts as the state of the world , and does not control information flow or packets sent in the gossip network. If (u,v)\in E , then u sends packets to v via a Poisson process with rate \lambda_{uv} , independent of all other processes in the network. For every time t\geq 0 , each node u stores a real number N_{u}(t) denoting the timestamp of its current packet. We initialize N_{u}(0)=0 for all u , and for all t\geq 0 the source maintains N_{0}(t)=t . When the Poisson clock (u,v) rings at time t , the counter of v updates as N_{v}(t)=\max\{N_{v}(t),N_{u}(t)\} . The age of information (AoI) of v is defined as X_{v}(t):=t-N_{v}(t) . It is helpful to think of the AoI as the time elapsed since the packet stored at node v was generated by the source. This model and variants have been studied extensively [ 4 , 5 , 6 , 7 , 8 , 9 , 10 , 3 ] , and we point the reader to a survey for more context [ 6 ] . Majority of the work in the area has used the stochastic hybrid system (SHS) framework, and the most well-known example of this is Yates’ recursive formula for the long-term expected age of a subset of vertices [ 10 , 3 ] which we briefly recall. Define the total rate of u into a subset of vertices S as \displaystyle\lambda_{u}(S)=\begin{cases}\sum_{v\in S}\lambda_{uv},&u\not\in S,\\ 0,&u\in S,\end{cases} (1) and let v_{S}=\lim_{t\to\infty}\mathbb{E}[\min_{u\in S}N_{u}(t)] be the long-term expected minimum age of any vertex in S . Then, for any subset S , Yates showed, \displaystyle v_{S}=\frac{1+\sum_{u\not\in S}\lambda_{u}(S)v_{S\cup\{u\}}}{\lambda_{0}(S)+\sum_{u\not\in S}\lambda_{u}(S)}. (2) Figure 1: A typical gossip network we consider. In general, the source does not have to update all vertices with the same rate. Similar recursive identities for the k th moments were recovered by Abd-Elmagid and Dhillon [ 11 ] . Letting v_{S}^{k}=\lim_{t\to\infty}\mathbb{E}\left[(\min_{u\in S}N_{u}(t))^{k}\right] be the long-term average k th moment of the age process, they proved, \displaystyle v_{S}^{k}=\frac{kv_{S}^{k-1}+\sum_{u\not\in S}\lambda_{u}(S)v^{k}_{S\cup\{u\}}}{\lambda_{0}(S)+\sum_{u\not\in S}\lambda_{u}(S)}. (3) Our contribution is to reprove these fundamental identities without the use of the SHS framework. The authors of [ 11 ] proved many other identities for the moment generating function of the age process, and generalized to joint moment identities. We comment on how our approach applies to the joint moment recursion in the conclusion. We also remark that ( 2 ) was generalized in [ 10 , eqn. (5)] to a source which self updates with rate \lambda_{e} ; this is perhaps the more well-known recursive formulation. Our analysis focuses on the standard AoI formulation instead of the version AoI, however our technique readily extends to this case. 1.1 Prerequisites and Contributions While the existing proofs of ( 2 ) and ( 3 ) are fairly short, they require the heavy machinery in the form of the SHS framework. Our contribution is a short proof of both identities from the first principles . Our proof relies on the recent connection between AoI in Poissonian gossip networks and the first passage percolation [ 12 ] . Let us first recall the definition of the first passage percolation. Let \gamma be any path in an edge-weighted directed graph G=(\mathcal{N},E,w) , where the weights may be random variables. Then, define T_{G}(\gamma)=\sum_{e\in\gamma}w_{e} as the passage time of \gamma . The first passage time from u to v is defined as T_{G}(u,v)=\min_{\gamma}T(\gamma) , where the minimum is over paths with u as the starting node and v as the final node. For any two subsets of vertices S,S^{\prime} , the passage time from S to S^{\prime} is naturally T_{G}(S,S^{\prime})=\min_{u\in S,v\in S^{\prime}}T_{G}(u,v) . Note that if G is finite and the weights w_{e} admit a density, then there is a unique path \gamma^{\prime} achieving T_{G}(S,S^{\prime}) almost surely. Given a gossip network G=(\mathcal{N},E) with Poisson clocks and update rates \{\lambda_{e}\}_{e\in E} , the authors of [ 12 ] construct an auxiliary weighted graph G^{\prime}=(\mathcal{N},E,w) on the same vertex and edge set, but with edge weights defined as w_{uv}=\operatorname{Exp}(\lambda_{uv}) , i.e., edge weights are exponential random variables with parameter corresponding to the associated Poisson process rate. It is important to note that while G^{\prime} has random edge weights there is no stochastic process associated to each edge, therefore, the first passage time between vertices can be computed. We make use of the following theorem, which relates the first passage time in G^{\prime} to the AoI of a vertex in G . Figure 2: A sample first passage path on a grid graph from the red vertex to the blue vertex. One can view the first passage time as the time a packet would take to travel from the red vertex to the blue vertex, along a minimizing random path. Theorem 1 ( [ 12 ] ) For any locally finite gossip network G=(\mathcal{N},E) and S\subset\mathcal{N} , a.s. there exists some time t_{0}<\infty such that for any t>t_{0} the age of information of S has distribution given by, X_{S}(t)=T_{G^{\prime}}(n_{0},S). (4) Theorem 1 was originally expressed in terms of a slightly different graph G^{\prime} with reversed edges, and t_{0} was excluded in favor of a more precise characterization of the age process. 1 1 1 The time t_{0} can be chosen explicitly by the following t_{0}=\inf\{t:u\text{ receives a timestamped packet from the source at time }t\} . This was necessary for the proof, but the weaker formulation above is sufficient for our purposes and we believe makes our presentation cleaner. In their original form, ( 2 ) and ( 3 ) only hold in the limit, therefore, our proofs are a modest strengthening of these results as they hold

Read the complete text