CS Paper Radar

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

Mohammad Moltafet, Nail Akar, Sennur Ulukus, Marian Codreanu, Roy D. Yates

cs.IT ·submitted 2026-11-04 21:24 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Distribution of Age of Information in the Erlang Loss System

cs.IT cs.PF ·2026-09-30 ·Nail Akar, Sennur Ulukus
similarity 0.73
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

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

Minimizing Age of Incorrect Information in Pull-Based Remote Estimation of a Markov Source

cs.IT cs.NImath.PR ·2026-10-15 ·Ismail Cosandal, Sennur Ulukus, Nail Akar
similarity 0.64
Abstract

In this paper, we consider a discrete-time pull-based remote estimation system involving an information source and a remote monitor where the information source is a finite-state irreducible discrete-time Markov chain (DTMC) process. In this system, the remote monitor sends a pull request towards the source which responds by sampling its process so as to transmit the sampled values towards the monitor through a delay channel, encapsulated in information packets. We consider i) zero delay (ZD) and ii) unit delay (UD) channels, where the packet transmission times are zero and one slot, respectively. For remote estimation, we use the maximum a posteriori (MAP) estimator, and for quantifying its performance, we use the mean age of incorrect information (MAoII) which is a recently proposed freshness and mismatch metric that penalizes an incorrect estimation along with its duration. Our goal is to obtain pull policies so as to minimize MAoII under a long-run sampling rate constraint. For the ZD model, we propose a semi-Markov decision process (SMDP) formulation of the problem, which allows us to find the optimum observation-dependent pull policy. On the other hand, the UD channel prevents the monitor from possessing perfect information on the actual AoII process at any given time, and the SMDP formulation of the ZD channel cannot readily be used for the UD model. For the system with the UD channel, we first provide a numerical algorithm to calculate the MAoII and the average sampling rate for a given observation-dependent pull policy. For the optimization of the underlying remote estimation system, we use the joint distribution of the age and source processes to be obtained from the history of all observations, termed as belief. Subsequently, we propose a belief-dependent policy obtained via the belief-MDP formulation and a constrained deep reinforcement learning (CDRL) algorithm.

0.11

Age of Incorrect Information for Pull-Based State Estimation of General Markov Sources

cs.IT cs.NI ·2026-08-13 ·Marco Zanni, Mohamad Assaad, Touraj Soleymani
similarity 0.64
Abstract

We study pull-based remote state estimation of an arbitrary, multi-state Markov source while accounting for both freshness and correctness attributes of information. To that end, we formulate a discounted optimization problem in terms of the age of incorrect information (AoII), and express it as a joint source-AoII belief Markov decision process (MDP) under maximum a posteriori (MAP) estimation. We then exploit the information structure of the model and prove that every reachable belief is represented by the last successfully observed source state and the number of time slots elapsed since that observation. For numerical computation, we truncate the elapsed no-success duration at a finite level and derive an explicit error bound and a criterion for selecting the truncation parameter. For reliable links, we show that an optimal policy can be represented by a look-up table of waiting times. For unreliable links, we propose a persistent policy and derive computable performance bounds. We also show that the MAP estimate stabilizes after a finite number of time slots. To further reduce memory requirements, we introduce a hybrid estimator with an early stationary switch and derive a computable bound on the resulting difference in performance. Finally, we extend the framework to multiple sources, formulate the scheduling problem as a restless multi-armed bandit, establish a sufficient condition for indexability, and develop an approximate Whittle index policy based on interpolation. Our numerical results illustrate the structure of the optimal single-source policy, evaluate the performance of the multi-source policies, and verify that the proposed heuristic policies closely approach the optimal solution while substantially reducing computational efforts.

0.04

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

Joint Freshness and Age-Dispersion Control over Finite-State Markov Wireless Channels

eess.SY cs.NIcs.PF ·2026-09-15 ·Aresh Dadlani, Hina Tabassum, Muthukrishnan Senthil Kumar, Masoumeh Moradian
similarity 0.62
Abstract · 6 pages, 5 figures

Age of information (AoI) has become a standard design objective for timely monitoring as it measures the freshness of the latest update at a receiver. AoI alone, however, is insufficient in goal-oriented applications where decisions depend on consecutive observations. Age dispersion complements AoI by measuring the generation-time separation between consecutive updates. In this paper, we study joint freshness and dispersion control for a generate-at-will status update link modeled as a finite-state Markov wireless channel. The objective is to minimize the long-run probability that either AoI or age dispersion exceeds a prescribed threshold under an average transmission rate constraint. For channel-dependent randomized transmission policies, we derive exact matrix expressions for the stationary joint distribution of AoI and dispersion. For reversible channels, mean dispersion is lower bounded by the reciprocal of the delivery throughput, and the difference is an explicit non-negative variance term for which we establish the exact equality condition. We then formulate the adaptive joint-threshold control problem as a constrained Markov decision process and prove that it admits an exact finite-state representation whose size scales linearly with the number of channel states and the threshold levels. Simulation results show that the controller reduces joint threshold violations by 37.3% relative to adaptive AoI-only control under the same transmission budget, while increasing mean AoI by 8.3%.

0.15

Semantic Freshness Optimal Sampling and Transmission for Gossiping Receivers

cs.IT cs.NIeess.SP ·2026-08-31 ·Irtiza Hasan, Ahmed Arafa
publishedtheory similarity 0.60
Abstract · To appear in IEEE ITW 2026

We study the optimal joint sampling and transmission policy for a transmitter communicating with two gossiping receivers that share information with each other, with the objective of tracking a source under the Version Age of Information (VAoI) metric. The transmitter can observe source-version changes, but it has to pay a sampling cost to get the current source information content. Similarly, it can communicate with a receiver by paying a transmission cost. Gossiping enables local information exchange and is able to reduce costly direct transmissions. With imperfect communication links, we formulate an infinite-horizon average-cost Markov Decision Process (MDP) to jointly minimize receiver VAoI, sampling cost, and transmission cost. Using Relative Value Iteration (RVI), we evaluate the optimal policy and establish several properties of its structure. We prove that sampling has a threshold structure in the transmitter VAoI. Among direct transmissions, it is optimal to serve the older receiver. We further characterize the transmit or idle decision through the receiver VAoI difference. Our analysis shows that link reliability and receiver VAoI imbalance have a significant effect on the optimal policy structure. Numerical results verify the structural properties and demonstrate the performance gains of the optimal policy over multiple baselines.

0.47

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