A General Formula for the Stationary Distribution of the Age of Information and Its Application to Single-Server Queues

Yoshiaki Inoue, Hiroyuki Masuyama, Tetsuya Takine, Toshiyuki Tanaka

Abstract

This paper considers the stationary distribution of the age of information (AoI) in information update systems. We first derive a general formula for the stationary distribution of the AoI, which holds for a wide class of information update systems. The formula indicates that the stationary distribution of the AoI is given in terms of the stationary distributions of the system delay and the peak AoI. To demonstrate its applicability and usefulness, we analyze the AoI in single-server queues with four different service disciplines: first-come first-served (FCFS), preemptive last-come first-served (LCFS), and two variants of non-preemptive LCFS service disciplines. For the FCFS and the preemptive LCFS service disciplines, the GI/GI/1, M/GI/1, and GI/M/1 queues are considered, and for the non-preemptive LCFS service disciplines, the M/GI/1 and GI/M/1 queues are considered. With these results, we further show comparison results for the mean AoI's in the M/GI/1 and GI/M/1 queues under those service disciplines.

Introduction

In modern status-update systems, such as sensor networks, financial tickers, or social media feeds, the "freshness" of information is a critical performance metric. This freshness is quantified by the Age of Information (AoI), defined as the time elapsed since the generation of the most recently received update. While prior research has extensively explored the mean AoI, average values often fail to capture the full operational picture. For instance, systems may maintain a low average age while experiencing unacceptable "age spikes" in mission-critical applications.

This work addresses the need for a comprehensive characterization of the entire probability distribution of AoI. By moving beyond simple averages, this framework enables engineers to calculate variance, tail probabilities, and non-linear age penalties, providing a more robust toolset for system design.

Methodology

The authors derive a general formula for the stationary distribution of AoI using a combination of sample-path analysis and ergodic theory.

The derivation begins by analyzing a single sample path of the AoI process, treating the system as a "marked point process." This leads to a fundamental relationship between the time-average of the AoI and the frequency distributions of system delay ($D$) and peak AoI ($A_{peak}$).

Evolution of the Age of Information (AoI) process $A_t$ over time.

Using the pointwise ergodic theorem, these sample-path results are translated into a general stationary distribution formula. The core result (Theorem 10) establishes that the probability density of the AoI, $a(x)$, is proportional to the difference between the cumulative distribution functions (CDFs) of the system delay and the peak AoI: $$a(x) = \lambda^\dagger (D(x) - A_{peak}(x))$$ where $\lambda^\dagger$ is the effective arrival rate. To facilitate practical application in queueing theory, the results are expressed using Laplace-Stieltjes Transforms (LST), allowing for the direct integration of standard queueing model results (e.g., M/GI/1, GI/M/1).

Key Insights

  • The "Peak" as a Fundamental Building Block: Peak AoI—the age reached just before an update is received—is shown to be a fundamental component of the entire AoI distribution, rather than just a secondary metric.
  • Universal Applicability: The derived formula is remarkably robust, holding "sample-path-wise." It applies regardless of specific service disciplines or the underlying distributions of arrivals and service times.
  • Variability Paradox: In certain scenarios, particularly FCFS queues, increasing arrival variability can paradoxically increase the AoI, even if throughput remains stable.
  • LCFS Superiority: For systems with exponential service times, preemptive Last-Come First-Served (LCFS) is shown to be optimal, as it prioritizes the freshest incoming data.

Results and Applications

The paper provides a comprehensive summary of LSTs and mean AoI formulas for various service disciplines, including FCFS, Preemptive LCFS, and Non-Preemptive LCFS (with and without discarding).

Summary of models and results derived using the general AoI formula.

Key findings include:

  1. Moments Formula: A simplified method for calculating the $k$-th moment of AoI, bypassing previously complex cross-term calculations.
  2. High-Load Behavior: Proof that as the arrival rate approaches infinity, the mean AoI converges to $1/h(0)$, where $h(0)$ is the value of the service time density at zero.
  3. Discipline Comparisons: Rigorous ordering of mean AoI performance across different disciplines for M/GI/1 and GI/M/1 systems.

Conclusion

This research provides a unified framework for analyzing information freshness across a wide array of queueing disciplines. While the current focus is on single-server queues, the general nature of the derived formula suggests potential extensions to multi-server systems or complex networks. Future work may also address assumptions regarding time-stamping, particularly in systems where pre-processing delays at the sensor are significant, or explore constraints such as energy harvesting.

Summary updated

Abstract

This paper considers the stationary distribution of the age of information (AoI) in information update systems. We first derive a general formula for the stationary distribution of the AoI, which holds for a wide class of information update systems. The formula indicates that the stationary distribution of the AoI is given in terms of the stationary distributions of the system delay and the peak AoI. To demonstrate its applicability and usefulness, we analyze the AoI in single-server queues with four different service disciplines: first-come first-served (FCFS), preemptive last-come first-served (LCFS), and two variants of non-preemptive LCFS service disciplines. For the FCFS and the preemptive LCFS service disciplines, the GI/GI/1, M/GI/1, and GI/M/1 queues are considered, and for the non-preemptive LCFS service disciplines, the M/GI/1 and GI/M/1 queues are considered. With these results, we further show comparison results for the mean AoI's in the M/GI/1 and GI/M/1 queues under those service disciplines.
BibTeX
@article{inoue2019general,
  author = {Yoshiaki Inoue and Hiroyuki Masuyama and Tetsuya Takine and Toshiyuki Tanaka},
  title = {{A General Formula for the Stationary Distribution of the Age of Information and Its Application to Single-Server Queues}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=YDEMs9Xzz_},
}
Figure