Preemption Revisited: Multi-Threshold Preemption Policies for AoI Minimization Sahan Liyanaarachchi1 , Sennur Ulukus1 , and Nail Akar2
arXiv:2605.16225v1 [cs.IT] 15 May 2026
1
University of Maryland, College Park, MD, USA 2 Bilkent University, Ankara, Türkiye
Abstract—The study of optimal preemption policies for status update systems has been a recurring topic in the age of information (AoI) literature, where threshold-based structures have been shown to be optimal under a generate-at-will update generation model under certain assumptions. In this work, we study the effectiveness of threshold-based policies for a system with random update arrivals. In this regard, we introduce an analytical framework for evaluating the AoI of multi-threshold preemption policies and present interesting characteristics of the structure of the optimal preemption policy. We show the effectiveness of these threshold-based policies over the traditional probabilistic preemption policies and single-threshold policies, where we observe that significant gains in terms of AoI can be obtained by utilizing both the age of the packet and the age of the system when designing these preemption policies.
I. I NTRODUCTION In this new era of modern computing, where the sheer volume of data processed in a single time unit is extreme, one fundamental problem lingers—upon arrival of a new job request, should we forgo our invested efforts on the current job and focus our efforts to this new job, i.e., preempt the job in service? This is a fundamental problem rooted in queuing theory and have been widely studied in the realm of status update systems, where service time of the queue models the delay experienced by the updates [1]. In such systems, the decisions on whether to preempt or not are made to maximize the freshness of the updates, which is often quantified through the age of information (AoI) metric [2]. This problem has been studied throughout the literature in multiple occasions. In [3], the authors aim to find the structure of the optimal preemption policy in the discrete-time domain under a generate-at-will model. They show that, under certain conditions, the optimal preemption policy has a doublethreshold structure. The work in [4] extends this study to the continuous-time domain with an impulse control framework. They show that threshold structures emerge naturally under a generate-at-will model. Under a random arrival update generation model, the work in [5] highlights the importance of probabilistic preemption policies for certain delay distributions. Reference [6] studies the problem of preemption under a random arrival model with the assumption that the intended service time of the new arrival is known before hand. Under this assumption, they show that threshold structures emerge in the optimal preemption policies. The work in [7] looks into preemption policies based on a single fixed threshold
under Poison arrivals. On a similar note, under a generate-atwill model, reference [8] focuses on finding optimal sampling policies by restricting preemption to a single-threshold policy. These works highlight the importance of threshold-based preemption policies. However, most of these works are restricted to single- or double-threshold policies for simplicity or focus on distributions where these policies are optimal. However, for general service time distributions, the optimal preemption policies are more complex. In fact, under certain service time distributions, the optimal preemption policies may be a mixture of multiple threshold policies depending on both the age of the system and the age of the packet in transmission. In this work, we restrict ourselves to a finite mixture of threshold policies. Under these policies, we give an analytical framework based on absorbing Markov chains (AMCs) to find the average AoI. We also give certain structural characteristics of these multi-threshold preemption policies. Using this framework, we show that these multi-threshold preemption policies outperform conventional probabilistic and single-threshold preemption policies. II. S YSTEM MODEL Consider a status update system operating in the discretetime domain, where new packets are generated at the beginning of a time-slot with probability q. We assume that the system is bufferless and hence any newly generated packet will be discarded if not subjected to the channel for transmission. The packets are transmitted across a random delay channel, where the discrete random variable Y represents the experienced delay. We assume that all channel transmissions occur at the end of a given time-slot. Let ∆n = n−Un denote the age of the system, i.e., the AoI at the receiver, where Un is the time-slot in which the most recently received packet was generated. Let δn = n − Gn denote the age of the packet (AoP) that is currently in transmission, where Gn denotes its generation time. If there is no packet in transmission, we say that the system is idle and AoP is not defined in this instance. As a control policy, we enforce the following preemption policy for the above system. Let {Γ(0) , Γ(1) , . . . , Γ(N ) } be a set of thresholds with Γ(0) = 0, Γ(N ) = ∞ and Γ(i−1) < Γ(i) for 1 ≤ i ≤ N . If Γ(i−1) ≤ ∆n < Γ(i) and δn = k, we (i) initiate a preemptive transmission with probability pk upon the generation of a new packet. If the system is idle, then a newly generated packet will be subjected to transmission with
(i)
probability p0 if Γ(i−1) ≤ ∆n < Γ(i) . We assume that any packet whose AoP goes beyond M is too stale and conveys no useful information to the receiver. Hence, if δn > M , that particular packet is discarded from the system and the system goes to the idle state. Now, we will find the average AoI of the system under the above class of preemption policies.
III. AO I A NALYSIS To model the AoI process, we consider one AoI cycle when in steady state. We consider a cycle which starts and ends with the successful reception of a packet under the above preemption policy. Let ∆n = γ at the beginning of this cycle. Since we discard packets whose age is greater than M , we have at most M possibilities for γ. For a given γ, we first find the average AoI of the cycle by constructing an absorbing Markov chain (AMC) which begins when the system is idle and gets absorbed when a packet is successfully delivered to the receiver. Let τγ denote the absorption time. Then, the cycle duration for this AoI cycle is τγ and the AoI increases from γ to γ + τγ − 1 in this particular cycle. Therefore, if ¯ can be πi = P(γ = i), then the average AoI denoted by ∆ found as follows, PM 2 1 i=1 πi 2iE[τi ] + E[τi ] ¯ (1) − . ∆= PM 2 2 i=1 πi E[τi ] ¯ we only need to find the pmf of γ and the Thus, to find ∆, first two moments of τγ . The AMC that models τγ is composed of M + 1 transient states one for each packet age and one for the idle state of the system. It will have M absorbing states depending on the age of the packet at the time of absorption. Since our preemption policy varies with ∆n , so does the probability transition matrix of our AMC. Let Pi denote the probability transition matrix of our AMC when Γ(i−1) ≤ ∆n < Γ(i) . Now, Pi can be represented as follows, S i Ai Pi = , (2) 0 IM where Si is an (M + 1) × (M + 1) matrix corresponding to the transitions between transient states, Ai is an (M + 1) × M matrix corresponding to the transitions from transient states to absorbing states, IM is an identity matrix of dimension M , and 0 is a matrix of all zeros of appropriate dimension. Let the states of the above transition matrix be ordered as {1S , 2S , . . . , MS , idle, 1A , 2A , . . . , MA }, where iS a is transient state with i denoting the age of the packet under transmission, iA is an absorbing state with i denoting the age of the packet when the packet is successfully received, and idle is a transient state which represents that there is no packet under transmission. Let yn = P(Y = n + 1|Y > n) be the conditional probability that the current transmission will be successful in the next time-slot, given n time units have elapsed. For brevity, we will drop the dependence on i and
(i)
define pk q = qk and the operator x̄ = 1 − x. Then, the matrices Si and Ai can be expressed as follows, q1 ȳ0 q̄1 ȳ1 0 ··· 0 0 q2 ȳ0 0 q̄2 ȳ2 · · · 0 0 .. .. .. . .. . .. .. . . . . Si = , qM −1 ȳ0 0 0 · · · q̄ ȳ 0 M −1 M −1 qM ȳ0 0 0 ··· 0 q̄M q0 ȳ0 0 0 ··· 0 q̄0 (3) q 1 y0 q̄1 y1 0 ... 0 q 2 y0 0 q̄ y . . . 0 2 2 .. .. .. .. .. . . . . . (4) Ai = . qM −1 y0 0 0 · · · q̄M −1 yM −1 qM y0 0 0 ··· 0 q 0 y0 0 0 ··· 0 Note, since Pi is a stochastic matrix, we have Si 1+Ai 1 = 1, where 1 represents a column vector of all ones of appropriate dimension. Now, the distribution of τγ is given in Proposition 1 and its proof is presented in Appendix A. Proposition 1 The distribution of τγ is given by, ! i−1 Y ζ (k) n−Γ(i−1) γ P(τγ > n) = α0 Sk Si γ 1,
(5)
k=0 (i)
(i)
(i)
(i−1)
< n ≤ Γγ , where Γγ = (Γ(i) − γ)+ , ζγ = for Γγ (0) (i−1) (i) , S0 = IM +1 , ζγ = 0, and α0 is a M + 1 Γγ − Γγ dimensional row vector of zeros with a one in the last entry. Now, with P(τγ > n) at hand, we can evaluate the first and second moments of τγ using Lemma 1 below. Lemma 1 The first and second moments of τγ is given by, E[τγ ] =
∞ X
P(τγ > k),
(6)
k=0
E[τγ2 ] = E[τγ ] + 2
∞ X
kP(τγ > k).
(7)
k=1
Lemma 1 follows from a standard result from probability theory. Now, substituting for P(τγ > k) and simplifying the expression in Lemma 1 using matrix geometric series, yields the following set of equations, ! ζγ(l) N −1 l−1 X Y ζ (k) X E[τγ ] =1 + α0 Skγ Slk 1 l=1
+ α0
N −1 Y
k=0 ζ (k)
k=1
!
Skγ
SN (I − SN )−1 1,
k=0
E[τγ2 ] =E[τγ ] + 2α0
N −1 Y k=0
ζ (k) Skγ
! SN (I − SN )−2 1
(8)
−1) + 2Γ(N α0 γ
N −1 Y
ζ (k) Skγ
!
C. Packet and System age-based Preemption (PSP)
SN (I − SN )−1 1
k=0
+ 2α0
N −1 X
l−1 Y
! ζγ(l) X ζ (k)
Skγ
k=0
l=1
(k + Γ(l−1) )Slk 1. γ
k=1
(9) Next, in Proposition 2, we show that πi s are the solution to the unique stationary distribution of a stochastic matrix. The proof of Proposition 2 is given in Appendix B. Proposition 2 Let π = {π1 , π2 , . . . , πM } be a row vector. Then, π satisfies the following, π = πB,
(10)
where B is a stochastic matrix and its elements are, ! (l) −1 N −1 l−1 X Y ζ (k) ζiX Bij =α0 Slk Al βj Ski l=1
+ α0
ζ
V. N UMERICAL R ESULTS
k=0
k=0 N −1 Y
(k)
Ski
! (I − SN )−1 AN βj
In this policy, we consider that the policy depends on both AoP and AoI. However, to simplify the policy, we only consider a single-threshold, i.e., N = 2, and moreover, we restrict our preemption probabilities to be deterministic. In particular, if 0 < ∆n < Γ then pk = p∗1 for 1 ≤ δn < δ1′ and pk = p∗2 for δ1′ ≤ δn ≤ M . If Γ ≤ ∆n < ∞ then pk = p∗3 for 1 ≤ δn < δ2′ and pk = p∗4 for δ2′ ≤ δn ≤ M . Further, p∗i ∈ {0, 1} for i = 1 to 4 and p10 = p2o = 1. The optimal parameters are found using an exhaustive search, where we have confined the search space for Γ to be less than 3M . Even though we use exhaustive search to find the optimal parameters for these policies, when the parameter space is ¯ one large, since we have the closed-form expressions for ∆, may resort to numerical optimization frameworks to find the locally-optimal parameters.
(11)
k=0
with βi being an M dimensional column vector of all zeros except for a one at the ith position. IV. P REEMPTION P OLICIES In this section, we identify interesting characteristics of an optimal preemption policy and formally introduce the lowcomplexity probabilistic and threshold policies considered in this work. Theorem 1 If N = ∞, then there exists an optimal determin(i) istic policy (i.e., pk ∈ {0, 1}). Theorem 2 If q = 1 and yn ≤ y0 for 0 < n < M , then the always preempt policy is optimal. Theorem 2 is identical to the result in [3] and may serve as an alternative proof that does not require an MDP formulation. The proofs of Theorem 1 and Theorem 2 are given in the Appendix C and Appendix D, respectively. A. Probabilistic Preemption (PP) In this policy, if the channel is idle, then any new generated packet will be transmitted with probability 1 and if the channel is currently transmitting a packet when a new packet arrives, then this old packet will be preempted with probability p∗ . The optimal p∗ is found using an exhaustive search. B. Packet Age-based Preemption (PAP) In this policy, we consider that the preemption policy only depends on AoP and hence N = 1 in this setting. Moreover, to simplify the policy further, we consider that p0 = 1, and pk = p∗1 for 1 ≤ δn < δ ′ and pk = p∗2 for δ ′ ≤ δn ≤ M . The optimal parameters for p∗1 and p∗2 and δ ′ are found through an exhaustive search.
In this section, we evaluate all the preemption policies considered in this work. To illustrate the differences between β them, we use the Weibull distribution where P(Y > k) = αk and set M = 8 to reduce the parameter space. We evaluate the three policies described in Section IV along with the always preempt policy (AP). In the first experiment, we set α = 0.9, β = 2 and vary the arrival probability q. As seen in Fig. 1, the AP policy exhibits the worse performance among the four policies. Moreover, despite the simplicity of the threshold-based preemption policies, they substantially outperform the PP policy by a good margin. Additionally, we see that PSP policy outperforms the PAP policy by a significant margin highlighting the importance of utilizing both the AoP and AoI for the design of the preemption policies. Next, we highlight some of few key structural features observed in these policies as we vary q for this particular distribution. First, we see that as q increases, the optimal preemption probability of the PP policy decreases. Additionally, we observe that the PAP policy would not preempt for low packet ages and would always preempt for higher packet ages. Further, the threshold δ ′ in which the PAP policy shifts between these two strategies increases as we increased q. In the PSP policy, we observe that the policy favors preemption at lower AoI values, whereas for higher AoI values, it favors preemption only at higher packet ages. As we increase q, the Γ at which it shifts between these two strategies decreases. These structural characteristics are very much dependent on the distribution of Y . Nevertheless, they highlight the importance of utilizing both the AoP and AoI for the design of the preemption policy. Finally, we compare how the preemption policies behave as we vary the β of the Weibull distribution. It is important to note that for, β < 1, the yn values are decreasing with n and are increasing if β > 1. Moreover, β = 1 corresponds to the geometric distribution. Fig. 2 illustrates the variation ¯ as we vary β for a fixed q. As seen, when β < 1, of ∆ all policies are identical to AP policy and as β increases they
(1)
7.5
(2)
Then, for Γγ < n ≤ Γγ , we have,
AP PP PAP PSP
P(τγ > n) = P(XΓ(1) ∈ S)P(Xn ∈ S|XΓ(1) ∈ S) γ γ (1) (1) Γ n−Γ 1M +1 γ γ T = α 0 0 M P1 P2 0M
7.0 6.5
Γ(1)
n−Γ(1) γ
ζγ(1)
n−Γ(1) γ
= α0 S1 γ S2
6.0
= α0 S1
6 1.6
1.8
1.4
1.6
2.0
2.2
AP PP PAP PSP
8 6 0.8
1.0
1.2
1.8
2.0
1.
(19)
P(Wn+1 = j|Wn = i)
2.2
=P(X∞ = jA |γ = i, X0 = idle)
¯ with β of the Weibull distribution with α = 0.9 and Fig. 2: Variation of ∆ q = 0.35.
start to diverge from the AP policy. This is a potential indicator that an equivalent condition to Theorem 2 can be obtained for q < 1 when yn s are decreasing.
=
N X
=α0
In this work, we give an analytical framework for computing AoI of multi-threshold preemption policies. Using our analytical framework, we show the importance of utilizing both AoI and AoP when designing these preemption policies. A PPENDIX A P ROOF OF P ROPOSITION 1 Let Xn denote the state of the AMC after n time units, and let S denote the set of transient states and A denote the set of absorbing states. Let 1M +1 be a column vector of all ones of dimension M + 1 and 0M be a column vector of all zeros of dimension M . Since the initial AoI is γ, the transition matrix of our non-homogeneous AMC will shift from Pi to Pi+1 (i) after Γγ time units has elapsed. Moreover, since our AMC always starts upon the successful reception of a packet, we have that the initial distribution our AMC is [α0 0TM ]. Now, (1) for n ≤ Γγ , we have, P(τγ > n) = P(Xn ∈ S|X0 = idle) (12) 1 (13) = α0 0TM P1n M +1 0M n Pn−1 k S 1M +1 1 k=0 S1 A1 = α0 0TM (14) 0M 0 IM (15)
(20)
P(XΓ(l−1) ∈ S, XΓ(l) = jA |X0 = idle) i
l=1 N −1 X
l=1
+ α0
(21)
i
l−1 Y
VI. C ONCLUSION
= α0 S1n 1.
(18)
Let Wn be the AoI after the nth successful reception of a packet. Note that, Wn forms a discrete-time Markov chain with M states and is irreducible if y0 > 0. If y0 = 0, we will have an irreducible chain with fewer states, which can be modeled accordingly. Either way, Wn has a unique stationary distribution which will be the distribution of γ. Let π be this stationary distribution. Next, we find the transition probabilities of Wn as follows,
7
10
1
A PPENDIX B P ROOF OF P ROPOSITION 2
¯ with the arrival probability q for α = 0.9 and β = 2. Fig. 1: Variation of ∆
12
(17)
Extending this argument for all i yields the desired result.
0.200 0.225 0.250 0.275 0.300 0.325 0.350 0.375 q
14
S2
(16)
(k) ζi
Sk
! ζ (l) −1 iX
k=0 N −1 Y
ζ
Slk Al βj
k=0 (k)
Ski
! (I − SN )−1 AN βj
(22)
k=0
=Bij .
(23)
Therefore, π satisfies, π = πB. A PPENDIX C P ROOF OF T HEOREM 1 Let Γi = i + 1 for i ≥ 1. Thus, each (∆n , δn ) is associated (i) with a unique pk preemption probability. Suppose in the (i) optimal policy, pk ∈ / {0, 1}. Thus, every time we reach the state (∆n , δn ) = (i, k), our AoI curve would branch based on whether we preempted or not. Let U1 denote the average area under the curve starting from state (i, k), until we reach state (i, k) again, if we took the preemption action at state (i, k). Similarly, define U2 to be the area, if we take the action not to preempt. Let V1 and V2 denote the expected cycle lengths for the above two scenarios. Then, we have, (i) (i) pk U1 + (1 − pk )U2 U1 U2 ¯ , . (24) ∆ = (i) ≥ min (i) V1 V2 pk V1 + (1 − pk )V2 V1 Since W is the average AoI of a policy which always 1 V2 preempts when (∆n , δn ) = (i, k), and W is the average AoI 2 for a policy which never preempts in the same state, we have
that one of the above two policies is better than or equal to (i) our optimal policy. Applying this to all pk ∈ / {0, 1}, we can contruct an equally optimal or better deterministic policy. A PPENDIX D P ROOF OF T HEOREM 2 If y0 = 1, the result is trivial. Now, consider the case y0 < 1. From (1), (6) and (7), we have that, ) ( E[τγ2 ] 1 ¯ (25) − ∆ ≥ min γ + γ 2E[τγ ] 2 P∞ E[τγ ] + 2 k=1 kP(τγ > k) 1 = min γ + − (26) γ 2E[τγ ] 2 P∞ kP(τγ > k) k=1 P∞ = min γ + . (27) γ 1 + k=1 P(τγ > k) P∞
kP(τ >k)
γ k=1 ¯γ = γ + P Let ∆ . Next, for a given γ, we 1+ ∞ k=1 P(τγ >k) ¯ γ . Let find the optimal preemption policy that minimizes ∆ ∗ ¯ this minimum value be denoted by ∆γ . Note that, τγ is the time for absorption starting from the idle state. Since we have fixed γ, our actions, i.e., the preemption probabilities, will depend only on the time elapsed since the AMC began and the current age of the packet. Thus, let pi,j denote the preemption probability given that the time elapsed is i and the packet age is j (j = 0 ≡ idle). Let zi,j be the probability that the packet age is j given the AMC has not been absorbed after i time units have elapsed. Then, z0,0 = 1. Now, given that the AMC has not been absorbed by time i, the probability that it will be absorbed in the next time step is given by xi = zi,0 pi,0 y0 + PM j=1 zi,j (pi,j y0 + p̄i,j yj ). Then, we have the following,
P(τγ > 0) = 1
(28)
P(τγ > k) = P(τγ > k − 1)P(τγ > k|τγ > k − 1)
(29)
= P(τγ > k − 1)(1 − xk−1 )
(30)
=
k−1 Y
(1 − xi ).
(31)
i=0
¯ γ is equivalent to the following optiNow, minimizing ∆ mization problem, P∞ Qk−1 k=1 k i=0 (1 − xi ) min . (32) P∞ Qk−1 pi,j ∈ [0, 1] 1 + k=1 i=0 (1 − xi ) Let the minimum of the above optimization problem be denoted by J(γ). In the above optimization problem, the xi s are correlated through the actions pi,j that we take. Further, note that, since yj ≤ y0 , we have that xi ≤ y0 for any feasible preemption policy. Hence, if we select the particular xi s independently subject to the constraint xi ≤ y0 , we can obtain a lower bound L(γ) such that J(γ) ≥ L(γ), where L(γ) is the solution to the following optimization problem, P∞ Qk−1 k=1 k i=0 (1 − xi ) min P∞ Qk−1 (33) xi ≥ 0 1 + k=1 i=0 (1 − xi ) s.t. xi ≤ y0 .
To obtain the lower bound, we first select an xi (say xj ) and find the optimizing xj for a given set of xi s for i ̸= j. To do this, we rearrange the above objective function as follows, P∞ Qk−1 k=1 k i=0 (1 − xi ) P∞ Qk−1 1 + k=1 i=0 (1 − xi ) Pj Qk−1 j + 1 + k=1 (j + 1 − k) i=0 (1 − xi ) =j+1− P∞ Qk−1 1 + k=1 i=0 (1 − xi ) P∞ Qk−1 k=j+1 (k − j − 1) i=0 (1 − xi ) + (34) P∞ Qk−1 1 + k=1 i=0 (1 − xi ) Pj Qk−1 j + 1 + k=1 (j + 1 − k) i=0 (1 − xi ) =j+1− P∞ Qk−1 1 + k=1 i=0 (1 − xi ) P∞ Qk−1 1 − xj+1 + k=j+3 (k − j − 1) i=j+1 (1 − xi ) + Pj Qk−1 (35) P∞ Qk−1 1+ k=1 i=0 (1−xi ) Qj + 1 + (1 − x ) i k=j+2 i=j+1 (1−x ) i=0
i
Pl with the convention that k=i operator results in zero for l < i. Next, we note that, xj is present only in the denominator of the second fraction through the term (1 − xj ) and in the 1 denominator of the third fraction as (1−x . To minimize the j) above expression, we need to maximize the magnitude of the negative fraction and minimize the magnitude of the positive fraction. This can be jointly achieved at the same time by setting xj = y0 . Therefore, for a fixed set of xi s (i ̸= j), we can minimize the above expression by setting xj = y0 and this choice is independent of the rest of the values we select for xi s. Therefore, xi = y0 ∀i achieves the minimum L(γ). Next, we note that if we set pi,j = 1 in (32), we get xi = y0 . Hence, the choice pi,j = 1 achieves the minimum of (32). Therefore, J(γ) is minimized by an always preempt ¯ ∗γ = γ + 1−y0 . Therefore, from (AP) policy. This yields that ∆ y0 ∗ ¯ ≥∆ ¯ . Finally, we observe that under an (27), we have that ∆ 1 ¯ = ∆∗ , under the AP policy. AP policy π1 = 1. Therefore, ∆ 1 This proves the desired result. R EFERENCES [1] S. K. Kaul, R. D. Yates, and M. Gruteser. Status updates through queues. In CISS, March 2012. [2] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus. Age of information: An introduction and survey. IEEE Journal on Selected Areas in Communication, 39(5):1183–1210, May 2021. [3] S. Banerjee and S. Ulukus. When to preempt in a status update system? In IEEE ISIT, July 2024. [4] A. Li, Y. Ince, and E. Uysal. Taming the heavy tail: Age-optimal preemption. Available online at arXiv:2601.16624. [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 IEEE ISIT, June 2025. [6] B. Wang, S. Feng, and J. Yang. When to preempt? age of information minimization under link capacity constraint. Journal of Communications and Networks, 21(3):220–232, June 2019. [7] S. Asvadi and F. Ashtiani. Delayed preemption: A new policy for balancing the age of information in prioritized networks. IEEE Transactions on Communications, 73(12):14639–14652, October 2025. [8] A. Arafa, R. D. Yates, and H. V. Poor. Timely cloud computing: Preemption and waiting. In Allerton Conference, September 2019.