Source-linked AI summary
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
TL;DR
The paper addresses why the mean AoI alone does not characterize long-run freshness behavior. It derives a general stationary-distribution formula in terms of system delay and peak AoI, then applies it across single-server queue disciplines. The formula supports a unified analysis of AoI distributions across the considered systems.
Problem
The mean AoI alone is insufficient to characterize the long-run behavior of AoI and related processes, while freshness matters in diverse information and communication systems.
Method
The paper derives a general stationary-distribution formula for AoI and applies it to single-server queues under FCFS, preemptive LCFS, and two non-preemptive LCFS disciplines.
Results
The stationary distribution of AoI is given in terms of the stationary distributions of system delay and peak AoI, regardless of service discipline or interarrival and service-time distributions.
Takeaways & Limitations
The formula provides a unified, efficient approach because system delay and peak AoI can be analyzed using standard queueing-theory techniques.
Takeaways & Limitations
The non-preemptive LCFS analysis described here relies on stability condition ρ < 1 and the stated regenerative-process assumptions.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper develops a general stationary-distribution formula for AoI and applies it to single-server queues across four service disciplines. It also derives queue-specific transforms, moments, bounds, ordering properties, and mean-AoI comparisons.
- Motivation: The full AoI distribution is needed beyond the mean because it characterizes deviations from the mean and supports analysis of related processes.Examples connect the AoI distribution to nonlinear age penalties and stationary estimation error for a Wiener process.
- General formula: The stationary AoI distribution is expressed through the stationary distributions of system delay and peak AoI under a fairly general setting.The relationship holds sample-path-wise regardless of service discipline or interarrival and service-time distributions.
- General formula: The general formula reduces ergodic queueing analysis to system-delay and peak-AoI distributions, which are accessible through standard queueing techniques.It also yields an alternative mean-AoI formula involving second moments of peak AoI and system delay.
- Single-server applications: The queueing applications cover FCFS, preemptive LCFS, and non-preemptive LCFS with or without discarding.The non-preemptive variants differ in whether overtaken packets remain for eventual service.
- Single-server applications: For FCFS queues, the paper derives distributional results for GI/GI/1 and explicit AoI LSTs for M/GI/1 and GI/M/1 models.It also provides upper and lower bounds for the FCFS GI/GI/1 mean AoI.
- Single-server applications: For preemptive and non-preemptive LCFS queues, the paper derives explicit AoI LSTs and obtains ordering or mean-AoI comparison results across service disciplines.Specialized formulas are also presented for M/M/1, M/D/1, and D/M/1 queues.
2 Sample-Path Analysis in a General Setting
The paper represents AoI sample paths through update times and post-update ages, then derives stationary AoI formulas for general FIFO systems under explicit ergodicity and stability assumptions.
- Sample-path construction: AoI sample paths are piecewise linear with slope one and downward jumps at information updates.The process is treated as right-continuous.
- Sample-path construction: The AoI between consecutive updates equals the post-update age plus elapsed time since the previous update.For t ∈[βn−1, βn), At = Xn−1 + (t −βn−1).
- Sample-path construction: Peak AoI is the age immediately before an update and equals the preceding post-update age plus the intervening update time.Apeak,n = Xn−1 + (βn −βn−1).
- Generality: The framework permits arbitrary nonnegative post-update ages before specializing to queueing systems with time-stamps equal to packet arrival times.This supports settings such as networks of queues, uncertain time-stamps, and sensor-fusion updates.
- Assumptions: The general formula applies when update-time and post-update-age limits exist, update rates converge to a positive finite value, and the associated process is stationary and ergodic.Queueing applications additionally use informative-packet arrivals, stable departures, and arrival-time time-stamps.
- Queueing formulation: In FIFO queueing systems, Theorem 10 gives the AoI density, LST, and kth moment in terms of stationary peak AoI and system-delay quantities.The theorem also extends to systems with arbitrary service disciplines through a virtual FIFO system containing only informative packets.
3 Applications to Single-Server Queues
The paper applies its general AoI-distribution formula to single-server queues under FCFS, preemptive LCFS, and non-preemptive LCFS disciplines. The resulting formulas characterize AoI distributions and mean-AoI behavior across several arrival and service models.
- Scope: The analysis covers FCFS, preemptive LCFS, and non-preemptive LCFS queues with and without discarding.The queueing models include GI/GI/1, M/GI/1, and GI/M/1 cases where specified.
- FCFS queues: The stationary AoI distribution is expressed through the system-delay distribution and peak-AoI distribution, enabling its application to FCFS queues.For FCFS GI/GI/1 queues, the paper gives an LST representation and derives bounds for the mean AoI.
- FCFS queues: For FCFS GI/GI/1 queues with Cv[G] ≤1, the mean AoI does not exceed the mean peak AoI.The paper also gives a counterexample showing this ordering does not hold generally.
- Preemptive LCFS queues: Preemptive LCFS AoI decomposes into three independent factors, and its mean is particularly favorable when service times are highly variable.With deterministic arrivals, the discipline is also effective for less variable service times; service-time variability can instead increase mean AoI when Cv[H] ≤1.
4 Conclusion
The paper presents a general stationary-distribution formula for AoI and applies it across single-server queues and service disciplines, including mean-AoI comparisons.
- The general AoI stationary distribution is expressed using the stationary distributions of system delay and peak AoI.This provides a unified approach because both quantities can be analyzed with standard queueing techniques.
- The analysis covers FCFS, preemptive LCFS, and non-preemptive LCFS with and without discarding.The queueing models include the specified M/GI/1 and GI/M/1 cases, with GI/GI/1 also considered for FCFS and preemptive LCFS.
- The paper compares mean AoI in M/GI/1 and GI/M/1 queues under the considered service disciplines.
- The results provide a basis for analyzing AoI in more sophisticated information update systems.
A Summary of Results for Special Cases
The appendix collects simplified AoI formulas for M/M/1, M/D/1, and D/M/1 queues, covering multiple service disciplines and discarding variants.
- The special-case formulas are obtained from the general M/GI/1 and GI/M/1 results.M/M/1 formulas follow from either family, while M/D/1 and D/M/1 formulas follow from their corresponding families.
- FCFS queues: ρ ≈0.6291 minimizes E[A] in the FCFS M/D/1 queue.The explicit formula makes this minimizing load deducible, whereas prior work did not provide an explicit E[A] formula for this queue.
- FCFS queues: FCFS M/D/1 has strictly smaller E[A] than FCFS M/M/1 with the same E[H] and ρ, for 0 < ρ < 1.
- Preemptive LCFS queues: For preemptive LCFS M/M/1 with λ ≠ µ, the AoI distribution is a two-exponential mixture; when λ = µ, AoI is Erlang of order two.The distribution arises because AoI is the sum of independent interarrival and service times in this model.
B Proof of Lemma 18
The proof of Lemma 18 derives a covariance bound by combining Lindley’s recursion, conditional expectations, concavity, and Jensen’s inequality.
- Lindley’s recursion provides the starting relation for the proof of Lemma 18.
- Combining the intermediate relations produces the covariance bound used in Lemma 18.The proof substitutes the derived relations into the covariance expression before applying the resulting lower bound.
- The argument decomposes E[G] by conditioning on G ≤ y and G > y.The conditional means satisfy E[G | G ≤ y] ≤ y ≤ E[G | G > y] when the upper tail has positive probability.
- Concavity of (y − x)x and Jensen’s inequality yield the needed conditional-expectation bound.
C Derivation of (47)
The derivation obtains the relevant transforms and moments by characterizing informative-packet waiting times, using independence, and substituting the resulting relations.
- The waiting time W_n of the nth informative packet is characterized through the remaining service time seen by the last arrived packet.
- W_n has a mixture representation with a zero-wait probability h*(λ) and a residual-service component otherwise.Its transform is then written as w*(s) = h*(λ) + λ/(s + λ)(1 − h*(s + λ)).
- Because service times are i.i.d. and non-preemptive, W_n and H†_n are independent.This independence is used to derive the next transform relation from the preceding formulas.
- Straightforward substitutions into the established equations yield (64), while differentiating a*(s) gives E[A].
D.2 Derivation of (65)
The derivation of (65) conditions peak-AoI analysis on whether an informative packet finds the system empty or nonempty, then combines the resulting conditional transforms. It also uses the stationary queue-state probabilities and joint transform of waiting and residual interarrival times.
- State decomposition: The stationary probabilities of zero and positive waiting states are expressed using q and g∗(µ).These probabilities provide the weights for the two conditional peak-AoI cases.
- Peak-AoI transform: Peak AoI is decomposed according to W_n = 0 versus W_n > 0 through conditional LSTs.The next peak AoI transform is formed by combining a∗_peak,0(s) and a∗_peak,+(s) with the corresponding state probabilities.
- Positive-waiting case: When W_n > 0, the waiting time has the conditional service-time distribution H<G given H < G.Here H is exponentially distributed with parameter µ, and the remaining interarrival time is G − H<G.
- Transform calculation: The joint LST f∗∗(s, ω) captures H<G and G − H<G, while its boundary value is obtained by taking ω → s + µ.The derivation uses this transform together with g∗ and the two conditional peak-AoI transforms.
D.4 Derivation of (67)
The derivation of (67) characterizes the queue length seen by arrivals and the waiting-time states of informative packets under non-preemptive LCFS without discarding. It then combines these cases to obtain the peak-AoI expression.
- Arrival-seen queue length: The non-preemptive LCFS queue-length distribution matches FCFS because the discipline is work-conserving.This identifies the arrival-seen queue distribution used in the derivation.
- Arrival-seen queue length: The queue length seen on arrival has geometric distribution Pr(L_A = k) = (1 − γ)γ^k for k = 0, 1, . . . .The parameter γ is the unique solution of equation (34).
- Informative-packet waiting: Informative packets have Pr(W = 0) = (1 − γ)/(1 − γg∗(µ)) and Pr(W > 0) = γ(1 − g∗(µ)).These cases correspond to arrivals finding the system empty or arriving during service without a subsequent arrival during the remaining service time.
- Peak-AoI transform: The peak-AoI transform is split into W_n = 0 and W_n > 0 cases, with additional non-informative packets accounted for in the positive-waiting case.The conditional transform for the empty-system case is obtained from equation (62).
E Proof of Theorem 33
The proof of Theorem 33 derives the mean-AoI expression for the M/GI/1 queue and extends it through a deterministic-arrival limiting argument. The limit uses τ → 0+ with λ = 1/τ.
- M/GI/1 case: For the M/GI/1 queue, the mean AoI is E[A] = 1/(λh∗(λ)).The section begins by rewriting equation (51) to obtain this expression.
- Proof conclusion: The theorem follows by applying the initial value theorem under the assumptions of Theorem 33.The initial value theorem is cited as the step connecting the transform representation to the stated result.
- D/GI/1 limit: The D/GI/1 case is analyzed by setting every interarrival time to τ and taking τ → 0+ while λ = 1/τ.The first two terms in the relevant expression converge to zero in this limit.
- D/GI/1 limit: The limiting calculation uses 1 − ζ = τ Pr(H > τ)/(1 − Pr(H > τ)).Continuity of h(x) is then invoked to complete the limit argument, regardless of whether h(0) is zero.
F Proof of Theorem 37
The proof establishes mean-AoI comparisons across service disciplines using formulas for the corresponding mean ages and an auxiliary function satisfying f(x) ≥ 1 for x ≥ 0.
- Service-discipline comparison: The inequality E[A_LCFS] ≤ E[A_FCFS] is verified from the stated mean-AoI formulas.The proof cites equations (38), (54), (69), and (71) for this comparison.
- Auxiliary inequality: The auxiliary function f(x) satisfies f(x) ≥ 1 for x ≥ 0 because f(0) = 1.The proof uses this inequality as part of the comparison argument.
- Remaining comparison: The proof then focuses on verifying the remaining non-preemptive LCFS comparison after the LCFS and FCFS inequalities are established.The cited passage indicates that only E[A_NP−W] requires an additional proof step.
- Proof conclusion: The derivation concludes after establishing the auxiliary relations involving b_n and the subsequent verification step.The supplied proof passages end with completion statements after these calculations.
G Proof of Theorem 38
The proof derives the target expression using earlier equations and a moment identity, then establishes positivity and monotonicity properties of the resulting function.
- The proof begins by combining equations (36), (51), and (106) to derive equation (72).
- The derivation uses E[H2] = (E[H])2((Cv[H])2 + 1) to rewrite the relevant second moment.
- The proof reduces the required inequality to checking nonnegativity of f1(x), with x = ρ2(Cv[H])2 ≥ 0.
- The denominator in equation (109) is shown to be positive for ρ ∈ (0, 1), supporting the subsequent sign analysis.
- For ρ ∈ (0, 2 − 2), v(ρ) decreases with ρ and approaches 1 as ρ tends to zero from above.