2023/07/17 by Arunabh Srivastava, Şennur Ulukuş, Srivastava, Arunabh +1 · 1 citation
Computer Science · Environmental Science · #Age of Information Optimization #FOS: Computer and information sciences #FOS: Electrical engineering #Health, Environment, Cognitive Aging #Information Theory (cs.IT) #Multiagent Systems (cs.MA) #Networking and Internet Architecture (cs.NI) #Opportunistic and Delay-Tolerant Networks #Signal Processing (eess.SP) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2307.08670
openalex publication_date 2023/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a gossip network consisting of a source generating updates and n nodes connected in a two-dimensional square grid. The source keeps updates of a process, that might be generated or observed, and shares them with the grid network. The nodes in the grid network communicate with their neighbors and disseminate these version updates using a push-style gossip strategy. We use the version age metric to quantify the timeliness of information at the nodes. We find an upper bound for the average version age for a set of nodes in a general network. Using this, we show that the average version age at a node scales as O(n(1)/(3)) in a grid network. Prior to our work, it has been known that when n nodes are connected on a ring the version age scales as O(n(1)/(2)), and when they are connected on a fully-connected graph the version age scales as O(log n). Ours is the first work to show an age scaling result for a connectivity structure other than the ring and fully-connected networks that represent two extremes of network connectivity. Our work shows that higher connectivity on a grid compared to a ring lowers the age experience of each node from O(n(1)/(2)) to O(n(1)/(3)).