CS Paper Radar

Optimal Preemption: Guaranteeing Information Freshness in Mean Age and Beyond

Aimin Li, Yiğit İnce, Elif Uysal

cs.IT ·submitted 2026-11-19 16:38 UTC · v1
theory

Abstract

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.

Comment
21 pages. Submitted to IEEE/ACM Transactions on Networking. Journal extension of the ISIT 2026 paper arXiv:2601.16624

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.76
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

Distribution of Age of Information in the Erlang Loss System

cs.IT cs.PF ·2026-09-30 ·Nail Akar, Sennur Ulukus
similarity 0.64
Abstract · 19 pages, 5 figures

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.

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.64
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

When Fresh Information Is Not Enough: Age-of-Actuation-Optimal Scheduling for Energy-Harvesting Actuators

cs.IT ·2026-10-15 ·Ali Nikkhah, Anthony Ephremides, Nikolaos Pappas
similarity 0.63
Abstract

We study transmission scheduling in an energy-harvesting actuation system where an actuation requires both a received update and available energy. While age of information (AoI) measures information freshness, age of actuation (AoA) measures the time elapsed since the latest completed actuation. The transmitter observes the receiver's AoA and battery state and decides whether to transmit a fresh update in each slot. We formulate average-AoA minimization as a Markov decision process and establish an AoA-threshold property for an optimal policy. We also derive the average AoA in closed form under the AoI-optimal policy, which is always-transmit. Numerical results show that AoA-aware scheduling can improve actuation freshness while reducing the number of transmissions, although information freshness may deteriorate. The two policies coincide for some pairs of channel success and energy-arrival probabilities. For a one-unit battery, the transmission rate under the AoA-optimal policy can vary nonmonotonically with the energy-arrival probability.

0.20

Optimal Regret for Online Storage Control via Cumulative Policies

eess.SY math.OC ·2026-09-18 ·Kamiar Asgari, Michael J. Neely
theory similarity 0.60
Abstract

We study online control of a scalar storage system with adversarial nonnegative arrivals, known retention coefficient, and convex costs depending on both state and action. Each action must respect current resource availability and is chosen before the current arrival and cost function are revealed. For the existing simplex disturbance-action policy class, we give an exact reparameterization by cumulative allocation fractions and a decay-weighted projected subgradient update. The resulting regret bound is independent of policy memory length. For fixed retention coefficient and cost constants, the controller achieves $O(\sqrt T)$ regret against the best fixed infinite-memory policy in this class, using $O(\log T)$ memory and arithmetic operations per round and one cost-subgradient query. A storage-specific block construction gives a matching lower bound against every causal feasible controller, including randomized controllers. Writing $τ=(1-α)^{-1}$, the minimax expected regret is $Θ(\sqrt T\min\{T,τ\}^{3/2})$ for every finite-memory simplex policy class and its infinite-memory extension, when $α\in[1/2,1)$, $T\ge4$, and the positive cost constants are fixed. This identifies the joint horizon and retention-time dependence for these policy benchmarks.

0.10

Worse Routes, Fresher Information: Preemption Redefines Which Route is Best

cs.IT ·2026-09-12 ·Adem Utku Atasayar, Aimin Li, Elif Uysal
published similarity 0.60
Abstract · 6 pages, 3 figures. Accepted at the Beyond AoI Workshop, ACM MobiHoc 2026. Version 2 adds acknowledgments and publication information

This paper studies joint sampling, route activation, and preemption control over $N$ heterogeneous transmission routes under a long-run objective combining Age of Information (AoI) with sampling and transmission costs. We formulate the problem as an average-cost impulse-control model, derive a vector-form integral average-cost optimality equation over a hybrid state space, and establish structural reductions on the state. We consider a two-route case and compute optimized policies using discretized policy iteration. Surprisingly, the results show that preemption can reverse routing preferences: the optimized policy may exclusively use a route with both a larger mean delay and a larger delay variance while avoiding the seemingly superior route. Relative to baselines that do not allow preemption, the proposed policy reduces average AoI by up to $96\%$.

0.41

Online Network Design with Maximum Delay and Stochastic Arrivals

cs.DS ·2026-11-10 ·Tianhang Lu
theory similarity 0.59
Abstract

We study online network services that combine pending requests into batches. Each batch pays for its spatial service and for the waiting time of its oldest request. The objective is the sum of these costs over all batches. Thus requests can share both a spatial purchase and one maximum-delay charge. We assume independent Poisson arrivals of known rates, while actual requests are revealed only upon arrival. For stateless services, suppose that each type has an attainable minimum cost when served alone, that every batch costs at least the stand-alone minimum of each type it contains, and that one finite-cost action can serve any batch, regardless of its request multiplicities. We give a deterministic algorithm with long-run ratio of expectations $e/(e-1)$ against an unrestricted offline optimum. This factor is optimal, even allowing randomization, already at one request location. The key comparison measures the union of time intervals associated with requests. The theorem applies directly to multi-root and pair aggregation on trees. We also study facility location, where each request pays its own connection distance and the bounded-action assumption can fail. A deterministic policy gives a ratio $3$ for arbitrary nonnegative opening costs. It immediately serves a finite initial set of requests, computes an assignment from their observed arrival gaps, and then keeps that assignment fixed. Its analysis combines Poisson insertion with a time-slice packing bound on the offline optimum. Every guarantee includes the full cost of completing finite inputs without an end-of-input signal.

0.15

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.59
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