PaperlayerView exact revision on arXiv

Source-linked AI summary

Distribution of Age of Information in the Erlang Loss System

Nail Akar, Sennur Ulukus

arXiv:2609.39667v1cs.ITcs.PFmath.IT

TL;DR

The paper addresses the limited availability of exact age distributions for general multi-server update systems, where freshness matters beyond conventional performance measures. It uses absorbing Markov chains to derive AoI and PAoI distributions under three policies, finding that identical occupancy behavior can coexist with different age distributions. For exponential service, PS requires the fewest servers for a desired age-violation probability, while NP performs least well; the multi-source analysis depends on other sources through their aggregate update rate.

  • Problem

    Exact age distributions for multi-server update systems have generally been limited, although they are needed for age-violation probabilities and general functions of age.

    Source: §1 · p. 3

  • Method

    The absorbing Markov chain method models a single AoI cycle to derive stationary AoI and PAoI distributions for NP, PR, and PS.

    Source: §1 · p. 3, §4.1 · p. 7

  • Results

    For a desired age-violation probability with exponential service, PS requires the fewest servers and NP is the least performing policy.

    Source: §6 · p. 17

  • Takeaways & Limitations

    A tagged source’s AoI and PAoI under self-preemption are affected by other sources only through their aggregate update rate.

    Source: §1 · p. 3, §6 · p. 17

    The observed policy ranking should not be extrapolated beyond exponential service times; preemption can become detrimental as service times approach deterministic.

    Source: §5 · p. 15

Abstract

from arXiv · show

In this paper, we study the exact distributions of the age of information (AoI) and peak AoI (PAoI) in a bufferless setting in which time-stamped updates, or processed tasks, generated by one or several information sources according to a Poisson process for each source, are submitted to a shared pool of $c$ homogeneous servers with exponentially distributed service times, i.e., the so-called M/M/c/c or the Erlang loss system. We consider three update management policies which come into play when a new update arrives to find all the servers busy: the arriving update is blocked (non-preemptive, NP) as in the Erlang loss system, or it preempts a randomly chosen update of its own source in service (preempt at random, PR), or the stalest such update (preempt the stalest, PS). All three policies preserve the same birth-death structure of the server occupancy process associated with the underlying Erlang loss system. However, their AoI and PAoI distributions can be very different. The approach we take is the absorbing Markov chain (AMC) method, in which a single AoI cycle, rather than the entire sample path of the system, is modeled by an absorbing Markov chain. Via the AMC method, we derive the exact distributions of AoI and PAoI in matrix-exponential form. The method extends to multiple sources sharing the same pool of servers, with the AoI of a given source being affected by the remaining sources only through their aggregate update rate. Numerical examples illustrate the implications of our findings, including distribution-based server provisioning under age violation constraints.

1 Introduction

The paper studies freshness in shared, bufferless multi-server update systems, where age of information captures what conventional delay, loss, and throughput metrics miss. It develops exact AoI and PAoI distributions under three policies and extends the analysis to multiple sources.

1 Introduction

  • The freshness metric is the elapsed time since the generation of the freshest update delivered to the monitor, because delay, loss, and throughput do not capture perceived timeliness.The setting includes processed tasks such as sensor readings, camera frames, and measurements used for monitoring or control.Source: §1 · p. 1
  • Unlike prior multi-server work focused on averages, this paper derives distributions for a shared pool with pool-level admission and preemption decisions.Related multi-server approaches cited in the introduction include average-AoI analyses for other server-selection and scheduling setups.Source: §1 · p. 3
  • The absorbing Markov chain method models one AoI cycle and uses Palm inversion to obtain stationary AoI and PAoI laws.This avoids relying on a recurrent-chain model of the full sample path, which does not directly capture AoI.Source: §1 · p. 3
  • Exact AoI and PAoI distributions are derived for NP, PR, and PS in multi-server Erlang loss systems, addressing a literature gap largely limited to averages.The distributions are matrix-exponential and phase-type, supporting arbitrary age-function averages and age-violation probabilities.Source: §1 · p. 3
  • The three policies share the same Erlang-B blocking probability but can have substantially different age distributions, which occupancy analysis cannot reveal.The paper therefore evaluates freshness at the age level rather than relying on occupancy alone.Source: §1 · pp. 2–3
  • For multiple sources, a tagged source is affected by other sources only through their aggregate update rate, with state-space size O(c^3) regardless of source count.The extension restricts preemption to updates belonging to the same source.Source: §1 · p. 3

2 Preliminaries

The preliminaries establish notation and describe absorbing Markov chains and matrix-exponential distributions. These tools underpin the paper’s exact AoI and PAoI distributional results.

2.1 Notation

  • Bold uppercase letters denote real-valued matrices, uppercase letters random variables, and bold lowercase letters vectors; the text also specifies element, column, spectral-abscissa, zero-matrix, identity, and all-ones notation.Sizes are inferred from context when not subscripted.Source: §2.1 · p. 4

2.2 Continuous-time Absorbing Markov Chains

  • An absorbing Markov chain separates transient states from absorbing states, with the transient matrix encoding transient transitions and the exit-rate matrix encoding transitions to absorption.The initial probability vector specifies the starting distribution over transient states.Source: §2.2 · p. 4
  • The absorption time of an absorbing chain has a phase-type distribution, while a matrix-exponential distribution allows a more general representation whose defining vectors and matrix need not have probabilistic interpretations.The paper’s AoI and PAoI distributions are matrix-exponential and are further shown to be phase type, making moments, transforms, and exponential tail decay rates available in closed form.Source: §2.2 · pp. 4–5

3 System Model

The system is a bufferless M/M/c/c pool in which updates begin service immediately when a server is free, and three policies govern arrivals to a full pool. Although these policies preserve the same occupancy process, they differ in update handling and freshness behavior.

3 System Model

  • With exponentially distributed service times, an admitted update immediately occupies one of c homogeneous servers; arrivals are Poisson with rate λ and the offered load is a = λ/µ.The source time-stamps each update, and no waiting room is present.Source: §3 · p. 5
  • The AoI rises within a cycle from the service time of the last successful update until the next successful reception, when it drops; PAoI is the cycle peak.The cycle length is the interval between successive successful receptions, and obsolete receptions do not cause an AoI jump.Source: §3 · p. 5
  • Under NP, arrivals finding all servers busy are blocked, and the full-pool blocking probability is y_c from the Erlang loss occupancy distribution.The blocking probability is insensitive to service-time shape beyond its mean.Source: §3 · p. 5
  • Under PR, a full-pool arrival replaces a uniformly chosen in-service update; exponential service makes the replaced update’s remaining service time identically distributed to the new update’s service time.The paper states that this memoryless property means preemption incurs no penalty in that respect.Source: §3 · p. 6
  • Under PS, the stalest in-service update is replaced; unlike NP, this requires time-stamp awareness and ordering, while PR requires preemption capability.All three policies preserve the same birth-death occupancy process and blocking probability, despite potentially different age distributions.Source: §3 · p. 6
  • For multiple sources, preemption is restricted to updates from the arriving update’s own source when the pool is full.The system has N Poisson sources sharing the same c servers.Source: §3 · p. 6

4 Analytical Model

This section develops an absorbing Markov chain for a tagged admitted update’s AoI cycle and uses its transient dynamics to derive AoI and PAoI distributions across the update policies. It extends the analysis to multiple sources and discusses computational cost and limitations, including how other sources affect a given source’s age under self-preemption and the limits of service-time insensitivity for age distributions.

4.1 The AMC method

  • The AMC models a tagged update’s cycle: successful absorption time equals PAoI, and occupancy of its second stage marks the ages visited during that cycle.The chain is launched at the tagged update’s generation epoch; PASTA supplies its initial configuration distribution, and transient-matrix exponentials yield the distributions.Source: §4.1 · p. 7, §4.2 · p. 9

4.2 Non-preemptive Policy

  • For NP, the tagged-update AMC has two transient stages and successful or unsuccessful absorbing states; second-stage occupancy corresponds to an age cycle.Its states track in-service updates with timestamps earlier or later than the tagged update, and its initial probabilities are obtained from Erlang loss probabilities.Source: §4.2 · pp. 7–9
  • Under NP, both steady-state PAoI and AoI have matrix-exponential distributions, and both also admit phase-type representations.The PAoI distribution is the absorption-time law conditioned on successful absorption; the AoI density is based on transient occupancy of the second stage.Source: §4.2 · pp. 9–11

4.3 Preempt at Random Policy

  • For PR, full-system arrivals can replace a randomly selected update, and the AMC modifications preserve the AoI and PAoI distribution formulas used for NP.The initial vector conditions on admission with or without preemption.Source: §4.3 · p. 11

4.4 Preempt the Stalest Policy

  • For PS, a full-system arrival replaces the stalest update; the resulting AMC likewise uses the NP distribution formulas and initial vector specified for PR.When the tagged update is the stalest, it is replaced and the chain enters the unsuccessful absorbing state.Source: §4.4 · p. 12
  • For NP, PR, and PS, the transient matrix is permutation-similar to upper triangular, with real spectrum bounded above by max(-λ, -cµ).The upper bound is attained at states (0, 0, 2) and (0, c, 2).Source: §4.4 · p. 12

4.5 Extension to Multiple Sources

  • For source 1, other sources affect age only through aggregate rate λ′; exact aggregation under self-preemption lets the single-source AMC formulas apply with L=O(c^3), independent of N.Successful receptions delimit source-1 AoI cycles, and the initial vector follows from PASTA applied to source-1 arrivals.Source: §4.5 · pp. 13–14

4.6 Discussion

  • For one source, the AMC has L=c^2+2c transient states; sparse linear systems yield transforms and moments, while pdf evaluation requires e^(Ax).The authors describe both operations as routine for the moderate state-space sizes arising here, even for large c.Source: §4.6 · p. 14
  • Although Erlang occupancy and blocking are insensitive to service-time shape beyond its mean, mean AoI already depends on the full service distribution at c=1 [37].The AMC relies essentially on exponential-service memorylessness; quantifying age-distribution sensitivity remains open.Source: §4.6 · p. 14
  • The AMC can in principle extend to p-phase CPH service by tracking phase compositions, but state-space growth has polynomial degree increasing in p.The authors leave this extension for future work because notation becomes cumbersome and preemption may not help for some service distributions.Source: §4.6 · p. 14

5 Numerical Results

The numerical examples compare AoI distributions across the three policies, use age-violation probabilities to illustrate server provisioning, and optimize rate allocation between two sources. They also caution that the policy ranking depends on exponential service times.

Example 1

  • For the tested loads, PS has the lowest AoI complementary CDF, followed by PR and NP; all share decay rate min(λ, cµ), while NP can have an additional polynomial tail factor.The NP tail mechanism blocks fresh updates until stale updates drain from a full pool; preemption removes this Erlang-like feature.Source: §5 · p. 15
  • The favorable ranking of preemptive policies is tied to exponentially distributed service times and should not be extrapolated to general service-time distributions.For a single-server bufferless system, preemption can become detrimental as service times approach deterministic, and NP can outperform preemptive policies.Source: §5 · p. 15

Example 2

  • Preemptive policies meet every feasible age-violation target with one to three fewer servers than NP; the M/M/∞ floor makes some targets infeasible regardless of pool size.For λ = 6, the 10^-6 target is below the 4.56 × 10^-6 floor; for λ = 12, PR and PS meet it with six servers.Source: §5 · p. 15, Table 7 · p. 16, Figure 4 · p. 16

Example 3

  • At Λ = 16 and κ = 0.9, optimal shares are 0.788, 0.764, and 0.756 under NP, PR, and PS; PS weighted mean AoI is 0.449, about 34% below NP’s 0.678.NP tilts most aggressively toward the prioritized source in this example.Source: §5 · p. 16

6 Conclusions

The paper derives exact AoI and PAoI distributions for single-source Erlang loss systems under three update policies and extends the analysis to multiple sources. Its conclusions emphasize policy-dependent age outcomes and open directions for extending the model and establishing distribution orderings.

Conclusions

  • The absorbing Markov chain method yields exact matrix-exponential AoI and PAoI distributions for NP, PR, and PS in single-source multi-server Erlang loss systems.The distributions are also shown to be phase type through an explicit similarity transformation.Source: §6 · p. 16
  • For a desired age-violation probability, PS requires the fewest servers and NP is the least-performing policy in the reported comparison.Source: §6 · p. 17
  • In the multiple-source extension, a tagged source’s AoI and PAoI are affected by other sources through their aggregate update rate.Source: §6 · p. 17
  • Open directions include multi-source analysis of immediate-discarding policies, phase-type service times, cross-source preemption, and proving stochastic orderings among policy distributions.The sensitivity of age distributions to service-time distributions is also left for future work.Source: §6 · p. 17
Loading 2609.39667v1…