A source node forwards fresh status updates as a point process to a network of observer nodes. Within the network of observers, these updates are forwarded as point processes from node to node. Each node wishes its knowledge of the source to be as timely as possible. In this network, timeliness at each node is measured by an age of information metric: how old is the timestamp of the freshest received update. This work extends a method for evaluating the average age at each node in the network when nodes forward updates using a memoryless gossip protocol. This method is then demonstrated by age analysis for a simple network.
more »
« less
The Age of Gossip in Networks
A source node updates its status as a point process and also forwards its updates to a network of observer nodes. Within the network of observers, these updates are forwarded as point processes from node to node. Each node wishes its knowledge of the source to be as timely as possible. In this network, timeliness is measured by a discrete form of age of information: each status change at the source is referred to as a version and the age at a node is how many versions out of date is its most recent update from the source. This work introduces a method for evaluating the average version age at each node in the network when nodes forward updates using a memoryless gossip protocol. This method is then demonstrated by version age analysis for a collection of simple networks. For gossip on a complete graph with symmetric updating rates, it is shown that each node has average age that grows as the logarithm of the network size.
more »
« less
- Award ID(s):
- 1717041
- NSF-PAR ID:
- 10317083
- Date Published:
- Journal Name:
- 2021 IEEE International Symposium on Information Theory (ISIT)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper studies the “age of information” in a general multi-source multi-hop wireless network with explicit channel contention. Specifically, the scenario considered in this paper assumes that each node in the network is both a source and a monitor of information, that all nodes wish to receive fresh status updates from all other nodes in the network, and that only one node can transmit in each time slot. Lower bounds for peak and average age of information are derived and expressed in terms of fundamental graph properties including the connected domination number. An algorithm to generate near-optimal periodic status update schedules based on sequential optimal flooding is also developed. These schedules are analytically shown to exactly achieve the peak age bound and also achieve the average age bound within an additive gap scaling linearly with the size of the network. Moreover, the results are sufficiently general to apply to any connected network topology. Illustrative numerical examples are presented which serve to verify the analysis for several canonical network topologies of arbitrary size, as well as every connected network with nine or fewer nodes.more » « less
-
We consider a multicast network in which real-time status updates generated by a source are replicated and sent to multiple interested receiving nodes through independent links. The receiving nodes are divided into two groups: one priority group consists of k nodes that require the reception of every update packet, the other non-priority group consists of all other nodes without the delivery requirement. Using age of information as a freshness metric, we analyze the time-averaged age at both priority and non-priority nodes. For shifted-exponential link delay distributions, the average age at a priority node is lower than that at a non-priority node due to the delivery guarantee. However, this advantage for priority nodes disappears if the link delay is exponential distributed. Both groups of nodes have the same time-averaged age, which implies that the guaranteed delivery of updates has no effect the time-averaged freshness.more » « less
-
A source provides status updates to monitors through a network with state defined by a continuous-time finite Markov chain. An age of information (AoI) metric is used to characterize timeliness by the vector of ages tracked by the monitors. Based on a stochastic hybrid systems (SHS) approach, first order linear differential equations are derived for the temporal evolution of both the moments and the moment generating function (MGF) of the age vector components. It is shown that the existence of a non-negative fixed point for the first moment is sufficient to guarantee convergence of all higher order moments as well as a region of convergence for the stationary MGF vector of the age. The stationary MGF vector is then found for the age on a line network of preemptive memoryless servers. From this MGF, it is found that the age at a node is identical in distribution to the sum of independent exponential service times. This observation is then generalized to linear status sampling networks in which each node receives samples of the update process at each preceding node according to a renewal point process. For each node in the line, the age is shown to be identical in distribution to a sum of independent renewal process age random variables.more » « less
-
In this paper, we study the fundamental problem of gossip in the mobile telephone model: a recently introduced variation of the classical telephone model modified to better describe the local peer-to-peer communication services implemented in many popular smartphone operating systems. In more detail, the mobile telephone model differs from the classical telephone model in three ways: (1) each device can participate in at most one connection per round; (2) the network topology can undergo a parameterized rate of change; and (3) devices can advertise a parameterized number of bits about their state to their neighbors in each round before connection attempts are initiated. We begin by describing and analyzing new randomized gossip algorithms in this model under the harsh assumption of a network topology that can change completely in every round. We prove a significant time complexity gap between the case where nodes can advertise 0 bits to their neighbors in each round, and the case where nodes can advertise 1 bit. For the latter assumption, we present two solutions: the first depends on a shared randomness source, while the second eliminates this assumption using a pseudorandomness generator we prove to exist with a novel generalization of a classical result from the study of two-party communication complexity. We then turn our attention to the easier case where the topology graph is stable, and describe and analyze a new gossip algorithm that provides a substantial performance improvement for many parameters. We conclude by studying a relaxed version of gossip in which it is only necessary for nodes to each learn a specified fraction of the messages in the system. We prove that our existing algorithms for dynamic network topologies and a single advertising bit solve this relaxed version up to a polynomial factor faster (in network size) for many parameters. These are the first known gossip results for the mobile telephone model, and they significantly expand our understanding of how to communicate and coordinate in this increasingly relevant setting.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ISIT45174.2021.9517796
