CS Paper Radar

Distribution of Age of Information in the Erlang Loss System

Nail Akar, Sennur Ulukus

cs.IT cs.PF ·submitted 2026-09-30 13:04 UTC · v1

Abstract

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.

Comment
19 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Elapsed-Service-Time-Aware Preemption for Age of Information Minimization

cs.IT ·2026-11-04 ·Mohammad Moltafet, Nail Akar, Sennur Ulukus, Marian Codreanu, Roy D. Yates
similarity 0.73
Abstract

We study the age of information and peak age of information in status update systems with an arbitrary number of independent sources sharing a single server with generally distributed service times. We consider a general age-dependent self-preemptive policy in which an in-service update from source $c$ is preempted by a new same-source arrival with a probability $p_c(x)$ that depends on the elapsed service time $x$. This formulation subsumes the non-preemptive, fully self-preemptive, and probabilistically preemptive policies as special cases, and also accommodates threshold-based preemption. We develop a unified analytical framework based on non-homogeneous absorbing continuous-time Markov chains and semi-Markov chains to derive explicit expressions for the average age of information and peak age of information of each source under general per-source service-time distributions and age-dependent preemption rules. The framework applies to both single-source and multi-source systems and enables joint tuning of per-source preemption parameters. Numerical results for fifteen service-time distributions in the single-source setting reveal that the benefits of preemption depend strongly on the service-time hazard-rate structure, with threshold-based preemption providing its most notable additional gains over age-independent policies for distributions with unimodal hazard rates. For a dual-source system with lognormal service times, jointly tuned threshold-based preemption achieves lower sum average age of information and peak age of information than the considered age-independent policies, highlighting the importance of cross-source interactions in preemption decisions.

0.09

Optimal Preemption: Guaranteeing Information Freshness in Mean Age and Beyond

cs.IT ·2026-11-19 ·Aimin Li, Yiğit İnce, Elif Uysal
theory similarity 0.64
Abstract · 21 pages. Submitted to IEEE/ACM Transactions on Networking. Journal extension of the ISIT 2026 paper arXiv:2601.16624

Once a status update enters service, age-optimal policies must wait for it, even when heavy-tailed delays inflate the Age of Information (AoI). We develop a framework in which the sender may preempt the update in service and sample a fresh one, under general service-time distributions and explicit action costs. Our framework covers sources that generate updates at will as well as random update arrivals. Under nondecreasing age costs, we prove that, with preemption, a finite mean delay suffices for a finite average age even under infinite delay variance. We show the optimality of constant service-age thresholds from prior work for exponential service, and exhibit numerically that for general delays the optimal preemption rule depends on both the AoI and the elapsed service time. Under an action-cost budget, we further minimize the Value at Risk (VaR), which bounds the AoI except for a prescribed fraction of time, and the Conditional Value at Risk (CVaR), the mean AoI over that fraction. We reduce both to the same optimality equations without enlarging the state space. Under Pareto and log-normal delays, our algorithm TAILOR keeps the average cost bounded as delay variance grows, while optimal non-preemptive sampling diverges. With optimal preemption, a more variable network can allow fresher data than a steadier one of equal mean delay.

0.30

Fundamental Tradeoffs in Sampling, Transmission and Information Freshness: Instantaneous Feedback

cs.IT cs.NIeess.SY ·2026-11-16 ·Subhankar Banerjee, Sennur Ulukus
theory similarity 0.58
Abstract

We study a time-slotted generate-at-will status-update system over an erasure channel with transmission success probability $q$, subject to average sampling- and transmission-rate constraints $f_s$ and $f_r$, respectively. The sampler-transmitter pair jointly decides whether to idle, retransmit a stale packet, or replace it with a fresh sample. We derive a universal lower bound on the optimal average age of information, analyze a class of stationary randomized policies, and obtain an optimal policy within this class that provides a $4$-approximation guarantee. The joint problem reduces to the sampling-constrained problem when $f_s\leq qf_r$ and the transmission-constrained problem when $f_s\geq f_r$. For $qf_r<f_s<f_r$, we formulate a constrained Markov decision process (CMDP) and introduce the class $\barΠ$ of $(W,R)$ policies, where $W$ specifies a waiting threshold for transmission and $R$ specifies a packet-replacement threshold. We prove that, for every choice of Lagrange multipliers, the corresponding Lagrangian-relaxed Markov decision process admits an optimal policy in $\barΠ$. We then formulate a linear program (LP) over distributions of $(W,R)$ policies and prove that choosing a policy according to an optimal LP solution yields an optimal CMDP policy. Moreover, there exists an optimal LP solution assigning positive probability to at most three $(W,R)$ policies. Since $\barΠ$ is countably infinite, for every $ε>0$ we construct a finite subset $\barΠ_ε\subset\barΠ$ and show that the LP restricted to this set yields an $ε$-optimal policy. Finally, we derive a stronger pair of lower bounds by considering systems with only the sampling-rate or transmission-rate constraint. Using these bounds, we construct a policy randomizing among four $(W,R)$ policies with a $2$-approximation guarantee for $qf_r<f_s<f_r$.

0.12

Analysis of Triggered Packet Streams: A Matrix-Analytic Method for Exponential Triggering Delays

cs.PF math.PR ·2026-09-02 ·Mehran Rahnamania, Michel Mandjes, Farid Ashtiani
similarity 0.57
Abstract

In many communication networks, the transmission of a packet may automatically trigger the transmission of a subsequent packet from the same source after a (possibly random) delay, without requiring acknowledgment or feedback. Such behavior arises in multi-stage status updating, proactive protocols, and other applications where users generate causally dependent packet streams. In this paper, in order to analyze these systems, we introduce the $\mathrm{M^T/G/1}$ queue. In this model, primary customers arrive according to a Poisson process, and each primary customer triggers a secondary customer to join the queue after an independent delay. This arrival mechanism falls outside the scope of classical queueing models with renewal arrival processes. When the triggering delays follow an exponential distribution, we exploit the memoryless property to set up a tractable Markov description. By truncating the number of pending secondary customers, we derive a finite system of linear algebraic equations in the Laplace--Stieltjes transform domain and solve them using matrix-analytic methods. Based on the resulting workload distribution, we compute class-specific performance metrics using PASTA for primary customers and Palm conditioning for secondary customers. Finally, we validate the accuracy of this truncation through numerical experiments.

0.49

Structure-Aware Online Optimization of the Age of Information with Unknown System Statistics

cs.IT math.OC ·2026-10-09 ·Yoshiaki Inoue, Michel Mandjes, Liron Ravner
theory similarity 0.55
Abstract

Timely information dissemination is essential in modern communication systems, where low informational latency is critical for networked control, monitoring, and real-time decision-making. The Age of Information (AoI) has emerged as a fundamental metric for quantifying information freshness at the receiver. A key challenge in AoI optimization is selecting the update generation rate: infrequent updates lead to stale information, whereas overly frequent updates increase queueing delays. We develop a structure-aware, data-driven framework for adaptive AoI optimization modeled as single-server queues with unknown system statistics. Our key idea is to exploit analytical representations of the AoI gradient, which depend on a finite-dimensional collection of system quantities that can be estimated from observations collected during system operation. This reduces the online learning problem to estimating the quantities required by the gradient, rather than learning the AoI objective as a black box. We propose an online stochastic approximation algorithm that jointly estimates these quantities and optimizes the update generation rate. We prove almost sure convergence of the algorithm to the optimal update generation rate under mild regularity and moment conditions, despite the temporal dependence induced by the underlying queueing process. We demonstrate the framework in four representative incomplete-information settings, including FCFS queues with unknown service characteristics or hidden background traffic, a preemptive LCFS system with partial observations, and a generate-at-will system with threshold waiting.

0.24

Tandem Queues with Hybrid Abandonment in Heavy Traffic

cs.PF math.PR ·2026-10-08 ·Cameron Curtis, Izzy Grosof, Seyed Iravani
theory similarity 0.55
Abstract

Hybrid-abandonment systems, where jobs abandon from certain stages of service but not others, occur frequently in medical, service, and computing systems. Abandonment affects the heavy-traffic behavior of both the stages with and without abandonment. In contrast to existing heavy-traffic works that focus on cases where there is abandonment at either all stages or no stages, we focus on the heavy-traffic behavior for these hybrid-abandonment systems. We provide the first heavy-traffic characterization of the second queue length in a two-stage tandem queue with abandonment only in the first stage. We characterize the scaled mean of the second stage queue length and prove that the scaled second queue length is asymptotically exponentially distributed and asymptotically independent of the first stage queue length. We derive our results by analyzing Markovian arrival process queues with countably infinite phases. We do this by extending techniques used to analyze queues with Markov-modulated arrivals to the broader class of infinite Markovian arrival process queues. We prove asymptotic results for a more general infinite phase process condition, an infinite birth-death phase process, and the hybrid-abandonment tandem case. We also empirically demonstrate that our heavy-traffic approximations are good approximations across various system settings.

0.25

Analysis of Triggered Packet Streams: Stochastic Bounds on System Time under General Triggering Delays

cs.PF math.PR ·2026-10-29 ·Mehran Rahnamania, Michel Mandjes, Farid Ashtiani
theory similarity 0.55
Abstract

Many emerging communication systems increasingly involve devices that transmit packets in multiple causally dependent stages as part of an internal workflow, rather than waiting for receiver feedback. To analyze such systems, we recently introduced the $\mathrm{M^T/G/1}$ queue, in which primary customers arrive according to an exogenous Poisson process, and each triggers a secondary customer to join the queue after an independent random delay, called the \textit{triggering delay}. Our prior heuristic approximations assume identical exponential service times, and our matrix-analytic framework assumes exponential triggering delays. However, no exact analysis is available when both distributions are general. In this paper, we derive stochastic bounds, in the usual stochastic order, on the system-time distribution of each customer class under general triggering-delay and service-time distributions. The service times within each primary--secondary pair may be generally dependent. Using sample-path coupling and level-crossing arguments, we show that the stationary workload is stochastically sandwiched between those of two classical queues: a two-class $\mathrm{M/G/1}$ queue with independent Poisson arrivals (lower bound), and a batch-arrival $\mathrm{M^{[2]}/G/1}$ queue where each primary--secondary pair arrives simultaneously (upper bound). Notably, these bounds do not depend on the triggering-delay distribution, and they are asymptotically tight in the sense that the stationary workload converges in distribution to that of the lower- and upper-bound queues as the triggering delays diverge to infinity and converge to zero in probability, respectively. We translate these workload bounds into system-time bounds for each customer class. Simulation experiments support these bounds.

0.08

Collision-Free Schedule Acquisition through Slotted ALOHA: Scaling Laws and Fluctuations

cs.IT ·2026-09-09 ·Plínio Santini Dester
similarity 0.54
Abstract · Submitted to Wireless Networks

Decentralized networks can learn collision-free periodic transmission schedules, but acquisition can consume much of a finite operating horizon. We characterize acquisition in a reservation protocol for a fixed population of $n$ nodes and a period of $Γ_n\ge n$ slots. Initially, each node attempts independently in each slot with probability proportional to $1/n$. A success reserves a slot that the node reuses every $Γ_n$ slots, retaining it after collisions. Nodes use only their own acknowledgments and small local memory. An exact finite-population Markov reduction, independent of the arrangement of reserved slots, characterizes the time until every node has a distinct reservation. As $n\to\infty$, mean acquisition takes $O(n^2)$ slots when $Γ_n=n$ and $O(n\log n)$ slots when $Γ_n\sim(1+θ)n$, for fixed $θ>0$. With a fixed number $Γ_n-n$ of spare slots, the standard deviation of acquisition time has the same asymptotic order as its mean. If that number diverges while $Γ_n/n$ remains bounded, the ratio of standard deviation to mean tends to zero. A diverging sublinear number of spare slots yields $o(n^2)$ mean acquisition while long-run utilization, the fraction $n/Γ_n$ of slots with successful transmissions, tends to one. Simulations validate these laws and compare acquisition and delivered packets per slot with existing access protocols.

0.31