arXiv CSopen access

Squeezing the Most Out of Preemption for AoI Minimization: Single-source Case

Squeezing the Most Out of Preemption for AoI Minimization: Single-source Case Nail Akar1 , Mohammad Moltafet2 , Sennur Ulukus3 , Marian Codreanu4, and Roy D. Yates5 1

Bilkent University, Ankara, Türkiye Tennessee Tech University, TN, USA 3 University of Maryland, College Park, USA 4 Linköping University, Linköping, Sweden 5 Rutgers University, New Brunswick, NJ, USA

arXiv:2607.19216v1 [cs.IT] 21 Jul 2026

2

Abstract—In this work, we study a single-source single-server continuous-time status update system where the updates arrive according to a Poisson process and update service times are generally distributed. In our proposed setting, a preemption policy refers to one where a new update preempts the ongoing one with a probability depending on the age of the update in service. We first propose an analytical method to derive the average age of information (AoI) and average peak AoI (PAoI) for any such preemption policy. This analysis is then utilized to tune two particular preemption policies: (i) probabilistic preemption (PP), in which preemption takes place according to a fixed probability regardless of the update age, (ii) threshold-based preemption (TP), for which preemption is incurred when the update age exceeds a certain threshold, both using one-dimensional line search. The effectiveness of policy tuning for the PP and TP policies is validated using lognormal-distributed update service times.

I. I NTRODUCTION Information freshness has become a key concept for successful operation of networked control and monitoring systems. In this paper, we consider a monitoring system comprising an information source and a remote monitor, separated from each other by a network. At times, the source samples its associated random process and sends the updates through the network, which introduces a random delay that is modeled by a server with generally distributed service times. Among several metrics, age of information (AoI) has recently gained significant attention, as an information freshness metric, thanks to its obliviousness to the dynamics of the source process [1]– [3]. The AoI process held at the monitor keeps track of the time elapsed since the generation of the last received update. Consequently, the AoI process is a cyclic process which increases in time with a unit slope within a cycle, but is subject to an abrupt downward jump at update reception instances, upon which a new cycle begins. In our proposed setting, the AoI process is an asymptotically stationary and ergodic continuous-time, continuous-valued stochastic process, and our interest in this paper lies in finding its time average. On the other hand, the discrete-time, continuous-valued peak AoI (PAoI) process is obtained by sampling the AoI process just before update receptions [4], and we are interested in finding its time average as well.

Although status update systems with multiple sources and servers have been studied in the literature, we focus our attention in this paper on a single-source single-server update system where the update arrivals are Poisson, and update service times (or network delays) are independent and identically distributed. No particular distribution is assumed for the update service times which are assumed to have arbitrary distributions. Particularly, we study preemption policies where a new update preempts the ongoing one with a certain probability depending on the age of the update in service which is defined as the elapsed time in service for the ongoing update. The situation in which preemption can also be based on the instantaneous AoI process is left for future research. We propose a method to derive the average AoI and average PAoI for any such preemption policy. The proposed analytical method is then used to tune two preemption policies parameterized by a single parameter, by using one-dimensional line search. The first policy is the so-called probabilistic preemption (PP) policy, where preemption takes place according to a fixed probability which is oblivious to update age [5]. The second policy is threshold-based preemption (TP), where the new arriving update preempts the ongoing one once the update age exceeds a given threshold. Our main contributions are given below. We propose a method to derive the statistics of the lifetime of updates for generally distributed service times and update age-dependent preemption, using the theory of non-homogeneous absorbing CTMCs, which to the best of our knowledge, is novel. • The update lifetime statistics are then used to derive the average AoI and PAoI for the status update system. • Finally, we use the proposed analytical model to tune two preemption policies, namely probabilistic preemption and threshold-based preemption, both of which are characterized by a single parameter. Notable reductions in average AoI and PAoI are observed with the use of these two policies, provided they are tuned properly.

•

The paper is organized as follows. Related work is briefed in Section II. Section III formally describes the AoI and PAoI processes for a generic status update system. In Section IV, we

describe the system model. Section V presents the analytical method. Numerical results are presented in Section VI. We conclude in Section VII. II. R ELATED W ORK The average AoI is first obtained in [1] for single-source M/M/1, M/D/1, and D/M/1 queues with infinite buffer capacity and first come first serve (FCFS) scheduling, whereas [6] investigates the distribution of AoI and PAoI for the bufferless M/M/1/1 and the single-buffer M/M/1/2 systems, along with the M/M/1/2∗ model where the packet waiting in the queue is to be replaced by a fresh packet arrival. [7] presents results for the steady-state distributions of AoI and PAoI for a general class of single-source systems. There has also been substantial interest on preemptive status update systems. We first review the existing work on singlesource systems. The average AoI and PAoI for the preemptive last come first serve (LCFS) M/G/1/1 queue is studied in [8] where the service time is modeled by the gamma distribution. [9] investigates the distributions of AoI and PAoI in singlesource bufferless systems with probabilistic preemption while allowing phase type distributions for both inter-arrival and service times. The reference [10] derives upper bounds for the mean AoI for the G/G/1/1 queue as well as its preemptive version while showing that the bounds are close to actual values. The work in [5] studies the average AoI and PAoI for a preemptive server with generally distributed service times and presents advantages of probabilistic preemption for certain service time distributions. In [11], the authors consider a single-source generate-at-will status update system with generally distributed service times. They study a continuoustime joint sampling and preemption problem to minimize the AoI. Studies in the multi-source setting are now briefed. The work of [12] investigates an M/G/1/1 queue with preemption and computes a closed form expression for the average AoI and PAoI of each source, by using the detour flow graph. When service time distributions are phase type, the authors of [13] provide an algorithm to obtain the distributions of AoI and PAoI for a multi-source M/PH/1/1 model under probabilistic preemption. [14] investigates a multi-source M/G/1/1 queuing model considering a self-preemptive packet management policy, and derives the moment generating function (MGF) of AoI and PAoI. III. AO I AND PAO I We describe the AoI and PAoI processes for a generic status update system. Let Gk and Rk denote the instances at which the k th update is generated by the source and received by the monitor, respectively. Let Uk denote the system time of the k th successful update, i.e., Uk = Rk − Gk . Fig. 1 depicts a sample path of the AoI process ∆(t) (thick blue solid curve). During cycle-k, ∆(t) increases with unit slope from the value Uk at time Rk until the value Φk at time Rk+1 , when it abruptly drops to Uk+1 . On the other hand, the PAoI process Φk , k ≥ 0 is obtained by sampling the AoI process ∆(t) at the embedded

cycle-k Vk

∆(t)

cycle-(k + 1) Vk+1

Φk Φk+1 Φk−1 Uk Uk+2 Uk+1 Gk

Rk

Gk+1 Rk+1 Gk+2

Rk+2

t

Fig. 1. Sample path of the AoI process ∆(t). Only generation and reception instances of successful packets are shown.

time points just before receptions. Note that the AoI and PAoI processes are asymptotically stationary due to the random nature of the service times. Consequently, we let ∆ and Φ denote the steady-state random variables for the random process ∆(t) and Φk , respectively, with cdf F∆ (x) = limt→∞ P(∆(t) ≤ x) and FΦ (x) = limk→∞ P(Φk ≤ x) for x ≥ 0. Hence, Z 1 T ∆(t) dt , (1) E[∆] = lim T →∞ T t=0 K 1 X E[Φ] = lim Φk , (2) K→∞ K k=1

IV. S YSTEM M ODEL We consider a status update system involving a single source and a monitor in Fig. 2. The source sends update messages (or updates) towards the monitor by receiving service from a single server. The updates are generated according to a Poisson process with rate λ. The service time for an update, denoted by S, is generally distributed with pdf f (x), cdf F (x), and the hazard rate q(x) which is defined as, q(x) = lim

1

h→0 h

Pr(x < S ≤ x + h | S > x) =

f (x) , 1 − F (x) (3)

which is also known as the instantaneous conditional completion rate when the elapsed time of the service time (or update age) has the value x. The cumulative hazard function, denoted by Q(x) is given by, Z x Q(x) = q(t) dt = − ln(1 − F (x)). (4) 0

For the hazard rates and cumulative hazard functions of wellknown distributions and also their definitions, we refer the reader to [15]. When a new update message arrives, it immediately starts to receive service if the server is idle. When the server is busy serving an update when the new update arrives, we assume that the new update preempts the ongoing one with probability p(x) when the instantaneous age of the update is x. This general preemption policy contains some well-known

new arrival preempts update in service (age x) w.p. p(x)

Poisson(λ)

Source

Server

completed update

Monitor

hazard rate q(x)

arriving update is discarded w.p. 1 − p(x) Fig. 2. Status update system involving a single source, a server with general service time characterized with hazard rate q(x) and buffer management policy characterized with preemption probability p(x), and a remote monitor.

preemption policies as its sub-cases. When p(x) = 1 for all x, then we have a fully preemptive (FP) policy [13]. On the other hand, the case of p(x) = 0 for all x is called the nonpreemptive (NP) policy [13]. The probabilistically preemptive (PP) policy of [5] uses a fixed probability α for preemption, i.e., p(x) = α for all x. In this paper, we propose to use a threshold-based preemptive (TP) policy for which p(x) = 1 for x > τ for a given threshold τ , and is otherwise zero. The motivation behind the TP policy is that when the update age is relatively large, it may be advantageous to preempt it with a fresh packet since otherwise the next AoI cycle would begin from a very large value, despite the fact that the current packet has been served for some time. However, the optimum value of τ needs to be determined that will yield the minimum average AoI or PAoI. Our first goal is to devise a method to derive the average AoI and peak AoI for the update system characterized with the 3-tuple (λ, q(x), p(x)), which allows one to study a wide range of preemption policies. Our second goal is to use this general method to derive the optimum PP and TP policies. Since TP is characterized by a single parameter τ similar to PP which is characterized by a single probability α, line search techniques can be used for both to solve the optimum parameters τ and α, respectively. V. A NALYTICAL M ETHOD The analytical method proposed for the update system (characterized by the 3-tuple (λ, q(x), p(x))) consists of the following two steps. In the first step, we study the lifetime of a single update that receives service. Using this update lifetime statistics, we derive the average AoI and PAoI in the second step. A. Lifetime of an Update Let us consider an update u which receives service. The lifetime of the update u, denoted by T , is defined as the duration of time u receives service. This service will be over either because u is preempted with a new update, or the service completes on its own. In order to study T , we construct an

absorbing Markov chain (AMC) Y (x) with one transient state 0, and two absorbing states, namely preemption state 1 and completion state 2. The AMC Y (x) starts operation with the update u starting to receive service at time x = 0. Y (x) stays in the transient state 0 until absorption occurs into the state 1 when u is preempted with a new update arrival, or absorption occurs into state 2 when the service of u is complete without being preempted by another update. Therefore, the lifetime T amounts to the absorption time of the AMC Y (x). The nonhomogeneous generator for the AMC Y (x), denoted by G(x) is easy to write:   − (q(x) + λp(x)) λp(x) q(x) 0 0 0 . G(x) =  (5) 0 0 0 The probability that the AMC Y (x) is at state 0 at time x, denoted by π(x), is written as, Rx

π(x) = Pr(T > x) = e− 0 (q(t)+λp(t))dt ,

(6)

which is the unique solution to the first-order differential equation, d π(x) = − (q(x) + λp(x)) π(x), x ≥ 0. (7) dx Let p and q denote the absorption probability into the absorbing states 1 and 2, respectively. We can thus write, Z ∞ p = Pr(Y (∞) = 1) = π(x)λp(x) dx , (8) 0 Z ∞ q = Pr(Y (∞) = 2) = π(x)q(x) dx . (9) 0

Let Tp and Tq denote the lifetime of the update u conditioned on absorption into the preemption state 1 and completion state 2, respectively. We can write the pdf of Tp as, fTp (x) = fT |Y1 (x) =

1 π(x)λp(x), p

(10)

from which one can obtain the first two moments of Tp , namely E[Tp ] and E[Tp2 ]. Here, Y1 refers to the event

{Y (∞) = 1}. Similarly, we write the pdf of Tq as, fTq (x) = fT |Y2 (x) =

1 π(x)q(x). q

= (11)

by means of which we can obtain E[Tq ] and E[Tq2 ]. Similarly, Y2 refers to the event {Y (∞) = 2}. B. Derivation of Average AoI/PAoI Consider the AoI cycle-k given in Fig. 1 for which ∆(t) rises up from the value Uk to Φk = Uk +Vk in a time duration of Vk . Note that Uk ∼ U and Vk ∼ V where U and V stand for the random variables corresponding to the system time of received updates, and the duration between two successful service completions, respectively. Here, A ∼ B when A and B have the same distribution, and further note that U and V are independent. The mean AoI E[∆] is then written as the ratio of the area under the AoI curve in one cycle to the duration of the cycle [3], E[V 2 ] E[∆] = E[U ] + . 2E[V ]

(12)

On the other hand, the mean PAoI E[Φ] is written as E[Φ] = E[U ] + E[V ].

(13)

Let us first note that U ∼ Tq since U amounts to the system time of a successful update. Hence, E[U ] = E[Tq ].

(14)

The study of the random variable V is more involved. Actually, V is the sum of three random variables, V = Va + Vp + Vq ,

(15)

where Va is the time needed until the first update arrival, Vp is the duration of all update lifetimes ending up with preemption, and Vq is the time needed for a successful update. Since Va is exponentially distributed with parameter λ, we have 1 1 (16) , Var(Va ) = 2 . λ λ On the other hand, Vp is written as the following sum, E[Va ] =

Vp =

K X

Tp,i ,

(17)

i=1

, i ] si E[T p i=0 i! q
, = 2 1 − p 1 + E[Tp ]s + E[Tp2 ] s2 + R(s) 1−p

(18) (19)

Also, let us define the moment generating functions (mgf) HVp (s) = E[esVp ] and HTp (s) = E[esTp ]. Using the method of collective marks [16], we can write,
(20) HVp (s) = GK HTp (s) ,

(21) (22)

where the first two derivatives of R(s) vanish at zero. By differentiating the expression (22) with respect to s and evaluating the expression at s = 0, we obtain, E[Vp ] =

d pE[Tp ] HV (s) . = ds p 1−p s=0

(23)

By differentiating the expression (22) once more with respect to s and evaluating the expression at s = 0, we obtain d2 HV (s) , ds2 p s=0 pE[Tp2 ] 2p2 E[Tp ]2 = + , (1 − p)2 1−p Var(Vp ) = E[Vp2 ] − E[Vp ]2 . E[Vp2 ] =

(24) (25) (26)

Finally, Vq is the time needed for the service of a successful update, i.e., Vq ∼ Tq . Since Vq ∼ Tq , we can write E[Vq ] = E[Tq ],

Var(Vq ) = E[Tq2 ] − E[Tq ]2 .

(27)

Finally, we write from (15) the following, E[V ] = E[Va ] + E[Vp ] + E[Vq ],

(28)

Var(V ) = Var(Va ) + Var(Vp ) + Var(Vq ), 2

2

E[V ] = Var(V ) + E[V ] .

(29) (30)

Finally, we obtain the average AoI E[∆] and the average PAoI E[Φ] by plugging in the identities (14), (28), and (30) in the equations (12) and (13), respectively. VI. N UMERICAL R ESULTS In this section, we study the average AoI and average PAoI under the PP and TP policies using the preemption probability α, and preemption threshold τ , respectively, when the service time S is log-normal distributed with pdf fS (t) =

(log t−µ)2 1 √ e− 2σ2 , tσ 2π

(31)

for t > 0, µ ∈ (−∞, ∞), σ > 0. The service time mean and variance are written as, σ2

where K has a delayed geometric distribution with parameter p and Tp,i s are independent of each other and Tp,i ∼ Tp . The probability generating function (pgf) of K, denoted by GK (z) = E[z K ], can be written as, GK (z) = q + pqz + p2 qz 2 + · · · , q = . 1 − pz

q P ∞

E[S] = eµ+ 2 ,

2

2

Var(S) = e2µ+σ (eσ − 1).

(32)

The service time parameters are fixed to µ = 0.75 and σ = 0.75 as in [5]. Fig. 3a (resp. Fig. 3b depicts the average AoI for the PP policy (resp. TP policy) as a function of the preemption probability α (resp. preemption threshold τ ), for four different values of the update arrival rate λ. Similarly, the average PAoI is depicted for both policies in Fig. 3c and Fig. 3d. We have the following observations: • For PP, the average AoI is a unimodal function (see [17]) of the preemption probability α, i.e., there is exactly one point α∗ in the interval α ∈ [0, 1] for which the average AoI takes its minimum value, and when α < α∗

(a)

12

(b)

12

10

10

8

8

6

6

4

4 0

0.2

0.4

0.6

0.8

1

(c)

14

0

1

2

12

10

10

8

8

6

6

4

4

5

3

4

5

(d)

14

12

3

4 0

0.2

0.4

0.6

0.8

1

0

1

2

Fig. 3. (a) Average AoI vs α (PP) (b) Average AoI vs τ (TP) (c) Average PAoI vs α (PP) (b) Average PAoI vs τ (TP)

(resp. α > α∗ ), average AoI is a strictly decreasing function (resp. strictly increasing function) of α. Similar observations can be made for the average PAoI under PP. • There are efficient search algorithms for finding the minimum of unimodal functions, such as the Golden search (see, for example, [17], [18]), which we propose to use in this paper. • Also, for TP, average AoI is a unimodal function of the preemption threshold τ ∈ [0, ∞) which enables us to find the threshold τ ∗ giving rise to the lowest average AoI, again using the Golden search algorithm. ∗ • For PP, the optimum preemption probability α decreases with increased λ. On the other hand, for TP, the optimum preemption threshold τ ∗ increases with increased λ. • TP outperforms PP when the optimum threshold and probability parameters for both are employed. In the second numerical example, we study the same service time distribution and vary the update arrival rate λ for each value of which we obtain the optimum preemption probability α∗ for PP, and the optimum preemption threshold τ ∗ for TP, both using the Golden search algorithm. The percentage reduction in average AoI and average PAoI with the tuned PP and TP policies, along with the FP policy, with respect to the benchmark NP policy, are depicted in Fig. 4. The results show that TP outperforms the two preemptive policies FP and PP, for all values of λ, whereas we have observed reductions up

to 18.99% and 16.54% with respect to the benchmark nonpreemptive policy NP in terms of average AoI and average PAoI, respectively. We have also observed that the FP policy outperforms the NP policy in both metrics, except at very low arrival rates. Another observation is that the gap between the TP and PP policies is wider for the average PAoI metric compared to the average AoI. VII. C ONCLUSIONS We study a single-source single-server status update system with generally distributed service times. For the case of lognormal distributed service times, the well-known practices of either not preempting at all or always preempting are shown to end up in poor performance, in terms of average AoI or average PAoI. We have also shown that probabilistic preemption and threshold-based preemption policies with the employment of optimally tuned preemption parameters result in significantly improved AoI/PAoI performance. In particular, we have obtained up to 18.99% reduction in average AoI with the threshold-based policy in comparison to the nonpreemptive policy, where the former outperformed all the other studied policies for all the scenarios investigated in this paper. R EFERENCES [1] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in IEEE Infocom, March 2012.

(a)

20

(b)

20

15

15

10

10

5

0

FP PP TP

5

FP PP TP

0

-5

-5 1

2

3

4

5

1

2

3

4

5

Fig. 4. Percentage reduction in (a) average AoI (b) average PAoI, for the three policies FP, PP, and TP, the latter two policies tuned to perform optimally using Golden search.

[2] A. Kosta, N. Pappas, and V. Angelakis, “Age of information: A new concept, metric, and tool,” Foundations and Trends in Networking, vol. 12, no. 3, pp. 162–259, 2017. [3] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” IEEE Jour. Sel. Areas in Comm., vol. 39, no. 5, pp. 1183–1210, May 2021. [4] M. Costa, M. Codreanu, and A. Ephremides, “Age of information with packet management,” in IEEE International Symposium on Information Theory (ISIT), June 2014. [5] M. Moltafet, H. R. Sadjadpour, Z. Rezki, M. Codreanu, and R. D. Yates, “AoI in M/G/1/1 queues with probabilistic preemption,” in Proceedings of IEEE International Symposium on Information Theory (ISIT), Ann Arbor, MI, USA, June 2025. [6] M. Costa, M. Codreanu, and A. Ephremides, “On the age of information in status update systems with packet management,” IEEE Transactions on Information Theory, vol. 62, no. 4, pp. 1897–1910, 2016. [7] Y. Inoue, H. Masuyama, T. Takine, and T. Tanaka, “A general formula for the stationary distribution of the age of information and its application to single-server queues,” IEEE Transactions on Information Theory, vol. 65, no. 12, pp. 8305–8324, 2019. [8] E. Najm and R. Nasser, “Age of information: The gamma awakening,” in IEEE International Symposium on Information Theory (ISIT), 2016, p. 2574–2578. [9] N. Akar, O. Doğan, and E. U. Atay, “Finding the exact distribution of (peak) age of information for queues of PH/PH/1/1 and M/PH/1/2 type,” IEEE Transactions on Communications, vol. 68, no. 9, pp. 5661–5672, 2020. [10] A. Soysal and S. Ulukus, “Age of information in G/G/1/1 systems: Age expressions, bounds, special cases, and optimization,” IEEE Transactions on Information Theory, vol. 67, no. 11, pp. 7477–7489, 2021. [11] A. Li, Y. Ince, and E. Uysal, “Taming the heavy tail: Age-optimal preemption,” 2026. [Online]. Available: https://arxiv.org/abs/2601.16624 [12] E. Najm and E. Telatar, “Status updates in a multi-stream M/G/1/1 preemptive queue,” in IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2018, pp. 124–129. [13] O. Doǧan and N. Akar, “The multi-source probabilistically preemptive M/PH/1/1 queue with packet errors,” IEEE Transactions on Communications, vol. 69, no. 11, pp. 7297–7308, 2021. [14] M. Moltafet, M. Leinonen, and M. Codreanu, “Moment generating function of age of information in multisource M/G/1/1 queueing systems,” IEEE Trans. Commun., vol. 70, no. 10, pp. 6503–6516, 2022. [15] A. N. O’Connor, M. Modarres, and A. Mosleh, Probability Distributions Used in Reliability Engineering. Center for Risk and Reliability, University of Maryland, College Park, MD, USA, 2016. [16] L. Kleinrock, Theory, Volume 1, Queueing Systems. USA: WileyInterscience, 1975.

[17] F. Gerald, Curtis and P. O. Wheatley, Applied Numerical Analysis, 7th ed. USA: Pearson Education, 2004. [18] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes: The Art of Scientific Computing, 3rd ed. USA: Cambridge University Press, 2007.