More Like this

1. Minimizing content staleness in dynamo-style replicated storage systems

   https://doi.org/10.1109/INFCOMW.2018.8406971  

   Zhong, Jing; Yates, Roy D.; Soljanin, Emina (April 2018, 2018 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS): AoI Workshop 2018)

   Consistency in data storage systems requires any read operation to return the most recent written version of the content. In replicated storage systems, consistency comes at the price of delay due to large-scale write and read operations. Many applications with low latency requirements tolerate data staleness in order to provide high availability and low operation latency. Using age of information as the staleness metric, we examine a data updating system in which real-time content updates are replicated and stored in a Dynamo-style quorum-based distributed system. A source sends updates to all the nodes in the system and waits for acknowledgements from the earliest subset of nodes, known as a write quorum. An interested client fetches the update from another set of nodes, defined as a read quorum. We analyze the staleness-delay tradeoff in replicated storage by varying the write quorum size. With a larger write quorum, an instantaneous read is more likely to get the latest update written by the source. However, the age of the content written to the system is more likely to become stale as the write quorum size increases. For shifted exponential distributed write delay, we derive the age optimized write quorum size that balances the likelihood of reading the latest update and the freshness of the latest update written by the source. 

   more » « less
2. The Age of Gossip in Networks

   https://doi.org/10.1109/ISIT45174.2021.9517796  

   Yates, Roy D. (July 2021, 2021 IEEE International Symposium on Information Theory (ISIT))

   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
3. Timely Gossip

   https://doi.org/10.1109/SPAWC51858.2021.9593163  

   Yates, Roy D. (September 2021, 2021 IEEE 22nd International Workshop on Signal Processing Advances in Wireless Communications (SPAWC))

   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
4. The Age of Information in Networks: Moments, Distributions, and Sampling

   https://doi.org/10.1109/TIT.2020.2998100  

   Yates, Roy D. (May 2020, IEEE Transactions on Information Theory)

   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
5. Fundamental Bounds on the Age of Information in Multi-Hop Global Status Update Networks

   Farazi, Shahab; Klein, Andrew G.; Brown, D. Richard (January 2019, Age of Information Workshop (INFOCOM 2019))

   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